Home » PHP » PHP_Compat » Bug #9687

[2006-12-24 04:41 UTC] jo at durchholz dot org

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;