哪种方法是在两侧的两个数组之间查找和存储不存在的值的最佳和最有效的方法


Which is the best and the most efficient way to find and store non existent values between two arrays in both sides?

也许这个问题已经问了好几次了,但我找不到正确的答案,所以就这样吧。

我有两个数组:一个带有~135732元素,另一个具有~135730元素。我需要找到哪些项目在第一个项目上,但在第二个项目上没有,反之亦然,我不知道是否有简单的方法可以实现这一点。

这就是我要做的:

$countArr1 = count($arr1);
$countArr2 = count($arr2);
for($i=0; $i < $countArr1; $i++) {
    // Check whether current element on $arr1 is on $arr2 or not
    if (!in_array($arr1[$i], $arr2)) {
        // if it doesn't then add it to $newArr 
        $newArr[] = $arr1[$i];
    }    
}

那么我会对$arr2做同样但相反的操作。在中,巨大的阵列可能需要一段时间,也可能会占用内存或服务器资源,即使是从CLI执行的,那么在资源使用方面,哪种方法是最好、最高效的呢?

编辑

让我们稍微澄清一下。我从DB得到$arr1,而$arr2来自其他地方。因此,最大的想法是找出哪些项目需要更新,哪些项目需要添加,哪些项目也需要标记为过时。用不太常见的词来说:

  • 如果元素在$arr1上,但在$arr2上不存在,则应标记为已过时
  • 如果元素出现在$arr2中,则需要添加(创建)$arr1上不存在btu
  • 否则只需要更新该元素

足够清楚吗?请随时询问一切,以便在此上提供帮助

编辑2

根据@dakkaron的回答,我制作了这个代码:

// $arr1 and $arr2 are previously built
$sortArr1 = asort($arr1);
$sortArr2 = asort($arr2);
$countArr1 = count($sortArr1);
$countArr2 = count($sortArr2);
$i = $j = 0;
$updArr = $inactiveArr = $newArr = [];
echo "original arr1 count: ", count($arr1), "'n";
echo "original arr2 count: ", count($arr2), "'n";
echo "arr1 count: ", $countArr1, "'n";
echo "arr2 count: ", $countArr2, "'n";
while ( $i < $countArr1 && $j < $countArr2) {
    if ($sortArr1[$i] == $sortArr2[$j]) {
        //Handle equal values
        $updArr[] = $sortArr1[$i];
        $i++; $j++;
    } else if ($sortArr1[$i] < $sortArr2[$j]) {
        //Handle values that are in arr1 but not in arr2
        $inactiveArr[] = $sortArr1[$i];
        $i++;
    } else {
        //Handle values that are in arr2 but not in arr1
        $newArr[] = $sortArr2[$j];
        $j++;
    }
}
echo "items update: ", count($updArr), "'n", "items inactive: ", count($inactiveArr), "'n", "items new: ", count($newArr), "'n";

我得到了这个输出:

original arr1 count: 135732
original arr2 count: 135730
arr1 count: 1
arr2 count: 1
items update: 1
items inactive: 0
items new: 0

为什么排序计数返回1?

您可以使用array_diff的先锋:http://php.net/manual/en/function.array-diff.php

编辑

php函数构造比等效的用户定义构造更有可能执行得更好。搜索中我发现了这一点,但您的数组的大小要小得多,最后我认为您应该用候选解决方案对原型脚本进行基准测试。

请参阅我的最后一条评论。

我能想到的最好的解决方案是首先sort两个数组,然后从下到上比较它们。

  • 从两个数组中最低的元素开始,并对它们进行比较
  • 如果它们相等,就取它们,在两个数组中向上移动一个元素
  • 如果它们不同,请在数组中向上移动一个值较低的元素
  • 如果你到达了其中一个数组的末尾,你就完成了

排序之后,这应该需要大约O(n)的复杂性。

这是伪代码中的一段代码:

arr1 = ...
arr2 = ...
arr1.sort();
arr2.sort();
i1 = 0;
i2 = 0;
while (i1<arr1.length() && i2<arr2.length()) {
    if (arr1[i1]==arr2[i2]) {
        //Handle equal values
        i1++; i2++;
    } else if (arr1[i1]<arr2[i2]) {
        //Handle values that are in arr1 but not in arr2
        i1++;
    } else {
        //Handle values that are in arr2 but not in arr1
        i2++;
    }
}

除此之外,如果您不想自己实现它,只需使用array_diff

我能想到的最好的解决方案是sort第二个数组,并尝试使用binary search从第一个数组中查找值,这将需要O(nLog(n))复杂度

由于您的值是字符串,因此您可以利用PHP的数组实现,在内部使用带有O(1)的哈希表进行关键字查找:

$diff = [];
// A ' B
$lookup = array_flip($b); // O(n)
foreach ($a as $value) { // O(n)
    if (!isset($lookup[$value])) $diff[] = $value;
}
// B ' A
$lookup = array_flip($a); // O(n)
foreach ($b as $value) { // O(n)
    if (!isset($lookup[$value])) $diff[] = $value;
}

所以总的来说,它在空间和时间上都是O(n)。

当然,最后你应该对它进行基准测试,看看它是否真的比这里的其他解决方案更高效。

用第二个数组元素填充基于哈希表的dictionary/map(不知道它在PHP中是如何调用的),并检查第一个数组的每个元素是否都出现在这个字典中
通常复杂度O(N)

for A in arr2
   map.insert(A)
for B in arr1
   if not map.contains(B) then
         element B  is on $arr1 but doesn't exists on $arr2

注意,这种方法并不能解决您编辑的问题

中的所有问题