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-23 23:41 UTC Modified: 2007-04-15 06:43 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-23 23: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 06:43 UTC] aidan (Aidan Lister)
This bug has been fixed in CVS. If this was a documentation problem, the fix will appear on pear.php.net by the end of next Sunday (CET). If this was a problem with the pear.php.net website, the change should be live shortly. Otherwise, the fix will appear in the package's next release. Thank you for the report and for helping us make PEAR better. The inner loop was replaced in r1.6