php - 为什么 `array_diff_ukey`调用了那么多次比较函数？

Question

我执行了下面的代码，结果让我很困惑!

我将两个数组和一个名为“myfunction”的函数作为参数传递给 array_diff_ukey 函数。我看到 myfunction 被调用了 13 次(而它最多应该被调用 9 次)。更神奇的是，它还会比较同一个数组的键!在输出的两列中，我都看到键“e”，而只有第二个数组有它(其他一些键也是如此)。

function myfunction($a,$b) {
    echo $a . "   ".$b."<br>";
    if ($a===$b) {
        return 0;
    }
    return ($a>$b)?1:-1;
}

$a1=array("a"=>"green","b"=>"blue","c"=>"red");
$a2=array("d"=>"blue","e"=>"black","f"=>"blue");

$result=array_diff_ukey($a1,$a2,"myfunction");
print_r($result);

输出:

a   b
b   c
d   e
e   f
a   d
a   e
a   f
b   d
b   e
b   f
c   d
c   e
c   f
Array
(
    [a] => green
    [b] => blue
    [c] => red
)

查看它在 eval.in 上运行.

为什么 array_diff_ukey 对比较函数执行那么多不必要的调用？

Answer 1

好问题。事实上，实现的算法并不是最有效的。

可以找到 PHP 数组函数的 C 源代码 github . array_diff_ukey 的实现使用了一个 C 函数 php_array_diff，它也被 array_udiff、array_diff_uassoc 的实现所使用，和 array_udiff_uassoc。

如您所见，该函数具有以下 C 代码:

for (i = 0; i < arr_argc; i++) {
    //...
    zend_sort((void *) lists[i], hash->nNumOfElements,
              sizeof(Bucket), diff_key_compare_func, (swap_func_t)zend_hash_bucket_swap);
    //...
}

...这意味着每个输入数组都使用比较函数进行排序，解释您获得的第一系列输出，其中比较同一数组的键，第一列可以列出除第一列之外的其他键数组。

然后它在第一个数组的元素上有一个循环，在其他数组上有一个嵌套循环，并且——嵌套在其中——在每个数组的元素上有一个循环:

while (Z_TYPE(ptrs[0]->val) != IS_UNDEF) {
    //...
    for (i = 1; i < arr_argc; i++) {
        //...
        while (Z_TYPE(ptr->val) != IS_UNDEF && 
               (0 != (c = diff_key_compare_func(ptrs[0], ptr)))) {
            ptr++;
        }
        //...
    }
    //...
}

显然，对每个数组进行的排序并没有真正影响该算法，因为仍然将第一个数组的所有键与其他数组的所有键进行比较0 != 比较。因此该算法是 O(klogk + nm)，其中 n 是第一个数组的大小，m 是大小之和其他数组的大小，k 是最大数组的大小。通常，nm 项最重要。

只能猜测为什么选择这种低效算法，但看起来主要原因是代码的可重用性:如上所述，其他 PHP 函数也使用此 C 代码，这可能更有意义。不过，这听起来确实不是一个好借口。

PHP 中此(低效)array_diff_ukey 算法的简单实现(不包括所有类型检查、边界条件等)可能如下所示 mimic_array_diff_ukey 函数:

function mimic_array_diff_ukey(...$args) {
    $key_compare_func = array_pop($args);
    foreach ($args as $arr) uksort($arr, $key_compare_func);
    $first = array_shift($args);
    return array_filter($first, function ($key) use($key_compare_func, $args) {
        foreach ($args as $arr) {
            foreach ($arr as $otherkey => $othervalue) {
                if ($key_compare_func($key, $otherkey) == 0) return false;
            }
        }
        return true;
    }, ARRAY_FILTER_USE_KEY);
}

更高效的算法会使用排序，但也会从中受益并逐步遍历第一个数组的键，同时按升序逐步遍历其他数组的键顺序，一前一后——永远不必后退。这将使算法 O(nlogn + mlogm + n+m) = O(nlogn + mlogm)。

下面是该改进算法在 PHP 中的可能实现:

function better_array_diff_ukey(...$args) {
    $key_compare_func = array_pop($args);
    $first = array_shift($args);
    $rest = [];
    foreach ($args as $arr) $rest = $rest + $arr;
    $rest = array_keys($rest);
    uksort($first, $key_compare_func);
    usort($rest, $key_compare_func);
    $i = 0;
    return array_filter($first, function ($key) use($key_compare_func, $rest, &$i) {
        while ($i < count($rest) && ($cmp = $key_compare_func($rest[$i], $key)) < 0) $i++;
        return $i >= count($rest) || $cmp > 0;
    }, ARRAY_FILTER_USE_KEY);
}

当然，如果要改进 array_diff_ukey 并获得公平的运行时比较，则需要用 C 语言实现该算法。

查看三个函数(array_diff_ukey、mimic_array_diff_ukey 和 better_array_diff_ukey) eval.in .