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

Question

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

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

排序函数通常需要比较函数来确定正确的排序.由于array_udiff只是计算差异,确定每对是否相等的谓词函数似乎应该足够了.

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

Answer 1

对于实施php_array_diff)( (这对于许多用户空间数组函数提供实现)的工作原理是重用数量的内部的比较函数.

这是因为这些比较函数已经存在用于其他目的,并且满足手头所需的任务:确定两个项目是否相等.他们做了一些额外的工作是不重要的; 重要的是需要考虑的代码相对减少.(一个equals函数可以很容易地用比较函数来编写,或者作为一个单独的实体来编写,但现在你有两个函数来完成同样的工作.)

实际的实现也可以通过排序来实现.因此,您需要使用适合排序的比较算法,否则您将获得意外结果.例如:

$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使用纯快速排序,而PHP使用从llvm派生的快速排序实现,其中包括插入排序优化.

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