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

Question

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

比较函数将项目 A 与项目 B 进行比较。谓词函数将仅确定项目 A 是否等于项目 B。

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

为什么 array_udiff 使用比较函数而不是谓词函数？如果我改用谓词有关系吗？即我是否可以选择只使用 0 和 1 返回值来表示不平等和平等，而放弃 -1 可能性？这会对我的结果产生什么不利影响(如果有的话)？

Answer 1

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>= 当前的

因此，该算法依赖于所有正在排序的输入，并使用该事实(以及比较函数)，因此它只需检查每个输入数组中的每个元素一次。如果比较函数没有生成实际排序的数组，则算法失败，您会得到不好的结果。

HHVM 可能会产生不同的结果，因为 HHVM 使用不同的排序算法。 HHVM 使用 pure quicksort ，而 PHP 使用 quicksort implementation derived from llvm其中包括插入排序优化。

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