在 PHP 中查找两个大型数组之间差异的最佳方法

php arrays performance algorithm

2022-08-30 22:01:00

我有2个非常大的数组（大小约为2，500，000）。我需要找出这些数组之间的差异。通过差异，我的意思是我需要一个结果数组，其值在数组1中，但不在数组2中。我用过array_diff（），但需要半个多小时！

第一个数组来自一个数据库，第二个数组来自另一个数据库。它们不在同一数据库服务器上。数组的大小不同。我正在处理大量的手机号码。我需要找出那些在一个列表中，但不在另一个列表中的手机号码

数组是带有数字键的普通数组。比较代码如下：

$numbers_list = array_diff($numbers_list, $some_other_list);

有没有更好的方法来做到这一点？请帮忙。

答案 1

这是简单的算法。

翻转第一个数组。值将成为键。因此，重复的值将被丢弃。
翻转第二个阵列（可选）
检查第二个数组中的每个元素（如果它存在于第一个数组中）。

当您使用非常大的数组时，它将消耗大量内存。

这是我的实现，

$a = file("l.a"); // l.a is a file contains 2,500,000 lines
$b = file("l.b");

function large_array_diff($b, $a){
    // Flipping 
    $at = array_flip($a);
    $bt = array_flip($b); 
    // checking
    $d = array_diff_key($bt, $at);

    return array_keys($d);   
}

我使用4G内存限制运行它。3G也可以。刚刚测试。

$ time php -d memory_limit=4G diff_la.php

这花了大约11秒！

real    0m10.612s
user    0m8.940s
sys     0m1.460s

更新

以下代码的运行速度比上述函数快large_array_diff 2 倍。

function flip_isset_diff($b, $a) {
    $at = array_flip($a);
    $d = array();
    foreach ($b as $i)
        if (!isset($at[$i])) 
            $d[] = $i;

    return $d;
}

因为它不调用（1 次），并且 .因此，节省了大量的CPU周期。array_fliparray_diff_keyarray_keys

答案 2

好的，更新了，转换为字符串以进行良好的测量（如果我们可以使用整数而不是字符串，则会有很大的不同...）：

<?php
$start = microtime(true);
echo 'creating' . PHP_EOL;
$array1 = array();
$array2 = array();
for ($i = 0;$i < 2000000;$i++) {
    $array1[] = (string)rand(100000000, 999999999);
    $array2[] = (string)rand(100000000, 999999999);
}
echo (microtime(true) - $start) . PHP_EOL;
$start = microtime(true);
echo 'key diff flip' . PHP_EOL;
$array1f = array_flip($array1);
$array2f = array_flip($array2);
echo (microtime(true) - $start) . PHP_EOL;
$start = microtime(true);
echo 'key diff' . PHP_EOL;
$diff = array_diff_key($array1f, $array2f);
echo (microtime(true) - $start) . PHP_EOL;
$start = microtime(true);
echo 'sorting' . PHP_EOL;
$start = microtime(true);
sort($array1);
sort($array2);
$notin2 = array();
reset($array2);
echo (microtime(true) - $start) . PHP_EOL;
echo 'comparing' . PHP_EOL;
$start = microtime(true);
foreach ($array1 as $value) {
    while (current($array2) < $value) {
        if (next($array2) == false) break;
    }
    if (current($array2) != $value) $notin2[] = $value;
}
echo (microtime(true) - $start) . PHP_EOL;
echo 'plain diff' . PHP_EOL;
$start = microtime(true);
$diff = array_diff($array1, $array2);
echo (microtime(true) - $start) . PHP_EOL;
?>

字符串

creating
8.66658186913
key diff flip
3.07359004021
key diff
1.48775887489
sorting
48.4047858715
comparing
9.41756916046
plain diff
19.21976614

real    1m37.574s
user    1m34.970s
sys     0m1.676s

整数（已删除）：(string)

creating
4.69975805283
key diff flip
2.5843539238
key diff
1.4868490696
sorting
15.2628200054
comparing
5.62516498566
plain diff
101.688895941

real    2m18.090s
user    2m15.112s
sys     0m1.356s

令我惊讶的是... 讨厌整数似乎...array_diff