为什么array_udiff使用比较函数而不是谓词函数？

Question

为什么array_udiff使用比较函数而不是谓词函数？

phparrays

10

array_udiff 使用回调函数计算两个数组之间的差异，但它需要一个比较函数而不是一个谓词函数。

比较函数将项 A 相对于项 B 进行比较。谓词函数只会确定项 A 是否等于项 B。

排序函数通常需要使用比较函数来确定正确的顺序。由于 array_udiff 只是计算差异，因此似乎应该足够使用谓词函数来确定每对是否相等。

为什么 array_udiff 使用比较函数而不是谓词函数？如果我使用谓词函数代替，会有什么影响？即我能否选择使用返回值为 0 和 1 来表示不相等和相等，舍弃 -1 的可能性？这对我的结果有什么负面影响（如果有的话）？

- Quolonel Questions

2个回答

0

补充有序数组必须更便宜。如果不排序，将需要O(m*n)的时间。

- Alex Blex

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- jbafford · Accepted Answer

php_array_diff()的实现（为许多用户空间数组函数提供实现）通过重用一些内部比较函数来工作。

这是因为那些比较函数已经存在于其他目的中，并且满足手头所需的任务：确定两个项目是否相等。它们做一些额外的工作并不重要；重要的是需要考虑的代码相对减少。（可以很容易地通过比较函数编写相等函数，或者作为单独的实体，但现在你有两个函数来完成同样的工作。）

实际实现还通过sorting来工作。因此，您需要使用适合排序的比较算法，否则会得到意外的结果。例如：

$a = [0, 1, 2, 3, 4, 5, 6];
$b = [4];

print_r(array_udiff($a, $b, function($x, $y) {
    return $x <=> $y; //Sorting comparison function, correct
}));

print_r(array_udiff($a, $b, function($x, $y) {
    return $x != $y; // Equality test, incorrect
}));

提供

Array //Sorting comparison function, correct
(
    [0] => 0
    [1] => 1
    [2] => 2
    [3] => 3
    [5] => 5
    [6] => 6
)
Array // Equality test, incorrect
(
    [0] => 0
    [1] => 1
    [2] => 2
    [3] => 3
    [4] => 4 // equality test causes udiff to incorrectly include 4
    [5] => 5
    [6] => 6
)

这是因为 php_array_diff()算法的运用方式，基本上是这样的：

复制并排序所有输入数组
将输出OUT设置为第一个排序后的输入数组
对于SRC中的每个元素
- V是SRC当前元素的值
- 从第二个输入数组A开始，对于每个输入数组
  - 快进到下一个元素A > V，但如果我们超过一个等于V的元素时，请做个记号。
  - 如果找到了V的匹配项，则从OUT中移除它。
  - 如果没有找到（所以它留在输入数组中），则在SRC中快进，直到有一个新的V >= 当前的V

因此，该算法依赖于所有输入都已排序，并利用这一点（以及比较函数），以便只需检查每个输入数组中的每个元素一次。如果比较函数未导致实际排序的数组，则算法失败并且您将获得错误结果。

HHVM可能会产生不同的结果，因为HHVM使用不同的排序算法。HHVM使用pure quicksort，而PHP使用从llvm派生的快速排序实现，其中包括插入排序优化。

通常，不同的排序算法通过不同的方式到达相同的解决方案。也就是说，不同的算法会以不同的顺序、时间和数量比较元素。在比较函数不正确的情况下，这可能会对数组的最终顺序产生很大影响。