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    
Comments Add Comment Add patch

Anyone can comment on a bug. Have a simpler test case? Does it work for you on a different platform? Let us know! Just going to say 'Me too!'? Don't clutter the database with that please !
Your email address:
Solve the problem : 47 + 15 = ?

 [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;


 [2007-04-15 11:43 UTC] aidan (Aidan Lister)
This bug has been fixed in CVS. If this was a documentation problem, the fix will appear on by the end of next Sunday (CET). If this was a problem with the 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