Package home | Report new bug | New search | Development Roadmap Status: Open | Feedback | All | Closed Since Version 1.6.0a3

Bug #9687 array_*_key function(s) slow
Submitted: 2006-12-24 04:41 UTC
From: jo at durchholz dot org Assigned: aidan
Status: Closed Package: PHP_Compat (version 1.5.0)
PHP Version: Irrelevant OS:
Roadmaps: 1.6.0a1    
Subscription  


 [2006-12-24 04:41 UTC] jo at durchholz dot org (Joachim Durchholz)
Description: ------------ array_intersect_key has a time complexity of O(N * M), where N is the number of entries in the first array and M is the maximum number of entries in the other arrays. This kind of quadratic behaviour is inacceptable when the arrays get large. To check whether two arrays have matching keys, an array_key_exists check should result in O(M * log N) behavior. (This assumes that array_key_exists has O(log N) complexity, which I sincerely hope!!!) I get this code after "// Compare entries": $result = $args[0]; foreach ($result as $key => $value) { for ($i = 1; $i < $array_count; $i++) { if (! array_key_exists ($key, $args [$i])) { unset ($result [$key]); break; } } } return $result;

Comments

 [2007-04-15 11:43 UTC] User who submitted this comment has not confirmed identity
If you submitted this note, check your email.If you do not have a message, click here to re-send
MANUAL CONFIRMATION IS NOT POSSIBLE.  Write a message to pear-dev@lists.php.net
to request the confirmation link.  All bugs/comments/patches associated with this

email address will be deleted within 48 hours if the account request is not confirmed!