Лучший способ найти различия между двумя большими массивами в PHP

У меня есть 2 очень больших массива (размером ~ 2,500,000). Мне нужно найти разницу между этими массивами. По разнице я имею в виду, что мне нужен результирующий массив со значениями, которые находятся в массиве 1, но не в массиве 2. Я использовал array_diff(), но требуется более полутора часов!

Первый массив поступает из одного БД и второго массива из другого db. Они не находятся на одном сервере базы данных. Массивы не имеют одинакового размера. Я имею дело с огромным количеством мобильных номеров. Мне нужно узнать те мобильные номера, которые находятся в одном списке, но не находятся в другом списке

массивы - это обычные массивы с цифровыми клавишами. Код Diff выглядит следующим образом:

Есть ли лучший способ сделать это? Пожалуйста, помогите.

Ответы

Ответ 1

Это простой алгоритм.

Отразить 1-й массив. Значения станут ключами. Поэтому повторяющиеся значения будут отброшены.
Flip Второй массив (необязательно)
Проверить каждый элемент в 2-м массиве, если он существует в 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

UPDATE

После выполнения кода выполняется 2x быстрее, чем функция large_array_diff, указанная выше.

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

    return $d;
}

Потому что он не вызывает array_flip (1 раз), array_diff_key и array_keys. Из-за этого сохраняется множество циклов ЦП.

Ответ 2

ОК, обновлено, отличное отведение в строку для хорошей оценки (это делает LOT разницу, если мы можем использовать целые числа вместо строк...):

<?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 ненавидит целые числа, кажется...