¿Cómo funciona array_diff?

Question

¿Cómo funciona array_diff()? Obviamente no podría funcionar de la siguiente manera:

function array_diff($arraya, $arrayb) 
{ 
    $diffs = array(); 
    foreach ($arraya as $keya => $valuea) 
    { 
     $equaltag = 0; 
     foreach ($arrayb as $valueb)  
     { 
      if ($valuea == $valueb) 
      { 
       $equaltag =1; 
       break; 
      } 
     } 
     if ($equaltag == o) 
     { 
       $diffs[$keya]=$valuea; 
     } 

    } 
    return $diffs;       
}         //couldn't be worse than this 

¿Alguien conoce una solución mejor?

EDITAR @animuson:

function array_diff($arraya, $arrayb) 
{ 
    foreach ($arraya as $keya => $valuea) 
    { 
     if (in_array($valuea, $arrayb)) 
     { 
      unset($arraya[$keya]); 
     } 
    } 
    return $arraya; 
} 

Answer 1

ACTUALIZACIÓN

• see below para un mejor código/más rápido.

• El comportamiento de array_diff es mucho mejor en php 5.3.4, pero aún ~ 10 veces más lento que la función de Leo.

• También vale la pena señalar que estas funciones no son estrictamente equivalentes a array_diff ya que no mantienen las teclas de matriz, es decir, my_array_diff(x,y) == array_values(array_diff(x,y)).

/ACTUALIZACIÓN

Una solución mejor es utilizar hash maps

function my_array_diff($a, $b) { 
    $map = $out = array(); 
    foreach($a as $val) $map[$val] = 1; 
    foreach($b as $val) if(isset($map[$val])) $map[$val] = 0; 
    foreach($map as $val => $ok) if($ok) $out[] = $val; 
    return $out; 
} 

$a = array('A', 'B', 'C', 'D'); 
$b = array('X', 'C', 'A', 'Y'); 

print_r(my_array_diff($a, $b)); // B, D 

referencia

function your_array_diff($arraya, $arrayb) 
{ 
    foreach ($arraya as $keya => $valuea) 
    { 
     if (in_array($valuea, $arrayb)) 
     { 
      unset($arraya[$keya]); 
     } 
    } 
    return $arraya; 
} 

$a = range(1, 10000); 
$b = range(5000, 15000); 

shuffle($a); 
shuffle($b); 

$ts = microtime(true); 
my_array_diff($a, $b); 
printf("ME =%.4f\n", microtime(true) - $ts); 

$ts = microtime(true); 
your_array_diff($a, $b); 
printf("YOU=%.4f\n", microtime(true) - $ts); 

resultado

ME =0.0137 
YOU=3.6282 

¿Alguna pregunta? ;)

y, sólo por diversión,

$ts = microtime(true); 
array_diff($a, $b); 
printf("PHP=%.4f\n", microtime(true) - $ts); 

resultado

ME =0.0140 
YOU=3.6706 
PHP=19.5980 

que es increíble!

Answer 2

La mejor solución para saber cómo funciona para echar un vistazo a su código fuente ;-)
(Bueno, esa es una de las potencias de código abierto - y si ves alguna posible la optimización, puede enviar el parche ;-))

para array_diff, que debe estar en ext/standard - lo que significa, para PHP 5.3, que debería estar ahí: branches/PHP_5_3/ext/standard

Y, entonces, el archivo array.c parece un objetivo plausible; la función php_array_diff, línea 3381, parece corresponder a array_diff.

(Buena suerte de pasar por el código: esto es bastante larga ...)

Answer 3

Desde PHP: "Devuelve una matriz que contiene todas las entradas de matriz1 que no están presentes en ninguna de las otras matrices "

lo tanto, sólo comprueba array1 contra todos arrayN y los valores en array1 que no aparecen en ninguna de esas matrices serán devueltos en una nueva matriz.

No necesariamente necesita recorrer todos los valores de array1. Solo para todas las matrices adicionales, recorra sus valores y compruebe si cada valor es in_array($array1, $value).

Answer 4

user187291 sugerencia de hacerlo en PHP a través de tablas hash es simplemente genial! En una descarga de adrenalina tomado de esta idea phantastic, incluso encontré una manera de acelerarlo un poco más (PHP 5.3.1):

function leo_array_diff($a, $b) { 
    $map = array(); 
    foreach($a as $val) $map[$val] = 1; 
    foreach($b as $val) unset($map[$val]); 
    return array_keys($map); 
} 

Con el punto de referencia tomado de la publicación de user187291:

LEO=0.0322 leo_array_diff() 
ME =0.1308 my_array_diff() 
YOU=4.5051 your_array_diff() 
PHP=45.7114 array_diff() 

El retraso de rendimiento de array_diff() es evidente incluso en 100 entradas por conjunto.

Nota: Esta solución implica que los elementos en la primera matriz son únicos (o se volverán únicos). Esto es típico de una solución hash.

Nota: La solución no conserva los índices. Asigne el índice original a $ map y finalmente use array_flip() para conservar las claves.

function array_diff_pk($a, $b) { 
    $map = array_flip($a); 
    foreach($b as $val) unset($map[$val]); 
    return array_flip($map); 
} 

PD: me encontré con esto mientras que en busca de alguna array_diff() paradoxon: array_diff() tomó tres veces más larga para prácticamente la misma tarea si se usa dos veces en la secuencia de comandos.

Answer 5

Como esto se ha mencionado (ver la respuesta de @BurninLeo), ¿qué tal algo así?

function binary_array_diff($a, $b) { 
    $result = $a; 
    asort($a); 
    asort($b); 
    list($bKey, $bVal) = each($b); 
    foreach ($a as $aKey => $aVal) { 
     while ($aVal > $bVal) { 
      list($bKey, $bVal) = each($b); 
     } 
     if ($aVal === $bVal) { 
      unset($result[$aKey]); 
     } 
    } 
    return $result; 
} 

Después de realizar algunas pruebas, los resultados parecen ser aceptables:

$a = range(1, 10000); 
$b = range(5000, 15000); 

shuffle($a); 
shuffle($b); 

$ts = microtime(true); 
for ($n = 0; $n < 10; ++$n) { 
    array_diff($a, $b); 
} 
printf("PHP => %.4f\n", microtime(true) - $ts); 

$ts = microtime(true); 
for ($n = 0; $n < 10; ++$n) { 
    binary_array_diff($a, $b); 
} 
printf("binary => %.4f\n", microtime(true) - $ts); 

$binaryResult = binary_array_diff($a, $b); 
$phpResult = array_diff($a, $b); 
if ($binaryResult == $phpResult && array_keys($binaryResult) == array_keys($phpResult)) { 
    echo "returned arrays are the same\n"; 
} 

Salida:

PHP => 1.3018 
binary => 1.3601 
returned arrays are the same 

Por supuesto, el código PHP no pueden funcionar tan bien como el código C, por lo tanto, no hay Me pregunto si el código PHP es un poco más lento.

Answer 6

Parece que puede acelerarlo mucho más utilizando otra matriz en lugar de desarmar. Sin embargo, esto utiliza más memoria, lo que podría ser un problema para el caso de uso (no he probado las diferencias reales en la asignación de memoria).

<?php 
function my_array_diff($a, $b) { 
    $map = $out = array(); 
    foreach($a as $val) $map[$val] = 1; 
    foreach($b as $val) if(isset($map[$val])) $map[$val] = 0; 
    foreach($map as $val => $ok) if($ok) $out[] = $val; 
    return $out; 
} 
function leo_array_diff($a, $b) { 
    $map = $out = array(); 
    foreach($a as $val) $map[$val] = 1; 
    foreach($b as $val) unset($map[$val]); 
    return array_keys($map); 
} 
function flip_array_diff_key($b, $a) { 
    $at = array_flip($a); 
    $bt = array_flip($b); 
    $d = array_diff_key($bt, $at); 
    return array_keys($d); 
} 
function flip_isset_diff($b, $a) { 
    $at = array_flip($a); 
    $d = array(); 
    foreach ($b as $i) 
    if (!isset($at[$i])) 
     $d[] = $i; 
    return $d; 
} 
function large_array_diff($b, $a) { 
    $at = array(); 
    foreach ($a as $i) 
    $at[$i] = 1; 
    $d = array(); 
    foreach ($b as $i) 
    if (!isset($at[$i])) 
     $d[] = $i; 
    return $d; 
} 

$functions = array("flip_array_diff_key", "flip_isset_diff", "large_array_diff", "leo_array_diff", "my_array_diff", "array_diff"); 
#$functions = array_reverse($functions); 
$l = range(1, 1000000); 
$l2 = range(1, 1000000, 2); 

foreach ($functions as $function) { 
    $ts = microtime(true); 
    for ($i = 0; $i < 10; $i++) { 
    $f = $function($l, $l2); 
    } 
    $te = microtime(true); 
    $timing[$function] = $te - $ts; 
} 
asort($timing); 
print_r($timing); 

Mis tiempos son (PHP 5.3.27-1 ~ dotdeb.0):

[flip_isset_diff] => 3.7415699958801 
[flip_array_diff_key] => 4.2989008426666 
[large_array_diff] => 4.7882599830627 
[flip_flip_isset_diff] => 5.0816700458527 
[leo_array_diff] => 11.086831092834 
[my_array_diff] => 14.563184976578 
[array_diff] => 99.379411935806 

Las tres nuevas funciones se encontraron en http://shiplu.mokadd.im/topics/performance-optimization/