La mejor manera de encontrar diferencias entre dos matrices grandes en PHP

Question

Tengo 2 matrices muy grandes (de tamaño ~ 2,500,000). Necesito encontrar la diferencia entre estas matrices. Por diferencia quiero decir que necesito una matriz resultante con valores que están en la matriz 1 pero no en la matriz 2. He usado array_diff() pero ¡toma más de media hora!

La primera matriz proviene de una base de datos y una segunda serie de otra base de datos. No están en el mismo servidor de base de datos. Las matrices no son del mismo tamaño. Estoy lidiando con una gran cantidad de números móviles. Necesito encontrar esos números móviles que están en una lista, pero no están en otra lista

Las matrices son matrices normales con teclas numéricas. diff código es el siguiente:

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

¿Hay una mejor manera de hacer esto? Por favor ayuda.

Answer 1

Este es el algoritmo simple.

1. Flip 1st array. Los valores se convertirán en claves. Entonces los valores repetidos serán descartados.
2. Voltear 2a serie (opcional)
3. Verificar si cada elemento está en 2da matriz si existe en la 1ra matriz.

Como se trabaja con matrices muy grandes, que va a consumen una gran cantidad de memoria.

Aquí está mi aplicación,

$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); 
} 

lo corrió utilizando 4G límite de memoria. 3G también funciona. Solo probado.

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

¡Tomo aproximadamente 11 segundos!.

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

ACTUALIZACIÓN

siguiente código se ejecuta 2x más rápido que large_array_diff función indicada anteriormente.

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

    return $d; 
} 

Debido a que no llama array_flip (1 vez), y array_diff_keyarray_keys. Muchos de los ciclos de CPU se guardan debido a esto.

Answer 2

OK, actualizado, casting a la cadena para una buena medida (hace MUCHA diferencia si pudiéramos usar números enteros en vez de cadenas ...):

<?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; 
?> 

Cuerdas

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 

enteros (eliminado (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 

Para mi sorpresa ..... array_diff aborrece enteros que parece. ..