试图了解 array_diff_uassoc 优化

Trying to understand array_diff_uassoc optimization

似乎数组在 array_diff_uassoc 内部比较之前先排序。

这种方法有什么好处?

测试脚本

function compare($a, $b)
    {
    echo("$a : $b\n");
    return strcmp($a, $b);
    }

$a = array('a' => 1, 'b' => 2, 'c' => 3, 'd' => 4, 'e' => 5);
$b = array('v' => 1, 'w' => 2, 'x' => 3, 'y' => 4, 'z' => 5);
var_dump(array_diff_uassoc($a, $b, 'compare'));


$a = array('a' => 1, 'b' => 2, 'c' => 3, 'd' => 4, 'e' => 5);
$b = array('d' => 1, 'e' => 2, 'f' => 3, 'g' => 4, 'h' => 5);
var_dump(array_diff_uassoc($a, $b, 'compare'));


$a = array('a' => 1, 'b' => 2, 'c' => 3, 'd' => 4, 'e' => 5);
$b = array('a' => 1, 'b' => 2, 'c' => 3, 'd' => 4, 'e' => 5);
var_dump(array_diff_uassoc($a, $b, 'compare'));

$a = array('a' => 1, 'b' => 2, 'c' => 3, 'd' => 4, 'e' => 5);
$b = array('e' => 5, 'd' => 4, 'c' => 3, 'b' => 2, 'a' => 1);
var_dump(array_diff_uassoc($a, $b, 'compare'));

http://3v4l.org/DKgms#v526

P.S。排序算法似乎在 php7.

中发生了变化

排序算法在 PHP 7 中没有改变。元素只是以另一种顺序传递给排序算法以提高性能。

好吧,好处可能是最终执行速度更快。当两个数组都有完全不同的键时,你真的遇到了最坏的情况。

最坏情况下的复杂度是对数组进行两次排序,然后比较两个数组的每个键。 O(n*m + n * log(n) + m * log(m))

最好的情况是进行两次排序,然后进行与较小数组中的元素一样多的比较。 O(min(m, n) + n * log(n) + m * log(m))

在匹配的情况下,您不必再次与整个数组进行比较,而只需从匹配后的键开始。

但在当前的实现中,排序只是多余的。我认为 php-src 中的实现需要一些改进。没有彻底的错误,但实施很糟糕。如果你懂一些C:http://lxr.php.net/xref/PHP_TRUNK/ext/standard/array.c#php_array_diff (请注意,该函数是通过 php_array_diff(INTERNAL_FUNCTION_PARAM_PASSTHRU, DIFF_ASSOC, DIFF_COMP_DATA_INTERNAL, DIFF_COMP_KEY_USER);array_diff_uassoc 调用的)

理论

排序允许创建一些快捷方式;例如:

A      | B
-------+------
1,2,3  | 4,5,6

A 的每个元素只会与 B[0] 进行比较,因为已知其他元素至少与 B[0] 一样大。

另一个例子:

A      | B
-------+-------
4,5,6  | 1,2,6

在这种情况下,A[0] 与 B 的所有元素进行比较,但 A[1] 和 A[2] 仅与 B[2] 进行比较。

如果 A 的任何元素大于 B 中的所有元素,您将获得最差的性能。

练习

虽然上述对于标准 array_diff()array_udiff() 效果很好,但一旦使用键比较函数,它将求助于 O(n * m) 性能,因为 this change while trying to fix this bug .

上述错误描述了自定义键比较函数在与具有混合键(即数字和字符串键值)的数组一起使用时如何导致意外结果。我个人认为这应该通过文档解决,因为使用 ksort().

会得到同样奇怪的结果