php - multidimensional - ¿Cómo funciona array_diff?

comparar valores de 2 arrays php

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 sabe una mejor solución?

EDITAR @animuson:

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

Answer 1

¡La sugerencia del usuario 187291 para hacerlo en PHP a través de tablas hash es simplemente genial! En una oleada de adrenalina tomada de esta idea fantástica, incluso encontré una manera de acelerarla 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 del usuario 187291:

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 en el rendimiento de array_diff () es evidente incluso con 100 entradas por matriz.

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

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

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

PD: Encontré esto mientras buscaba array_diff () paradoxon: array_diff () tomó tres veces más tiempo para prácticamente la misma tarea si se usaba dos veces en el script.

Answer 2

ACTUALIZAR

• ver más abajo para un código más rápido / mejor.

• El comportamiento de array_diff es mucho mejor en php 5.3.4, pero todavía es 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 claves de matriz, es decir, my_array_diff(x,y) == array_values(array_diff(x,y)) .

/ACTUALIZAR

Una mejor solución es utilizar mapas hash.

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

punto de 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

¡Eso es increíble!

Answer 3

Como esto ha sido mencionado (ver la respuesta de @ BurninLeo), ¿qué pasa con algo como esto?

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 puede funcionar tan bien como el código C, por lo que no es de extrañar que el código PHP sea un poco más lento.

Answer 4

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

Por lo tanto, solo verifica array1 contra todo arrayN y cualquier valor en array1 que no aparezca en ninguno de esos arreglos se devolverá en un nuevo array.

Ni siquiera necesariamente tiene que recorrer todos los valores de array1 . Solo para todas las matrices adicionales, in_array($array1, $value) sus valores y verifique si cada valor es in_array($array1, $value)

Answer 5

La mejor solución para saber cómo funciona para echar un vistazo a su código fuente ;-)
(Bueno, ese es uno de los poderes del código abierto, y si ves alguna optimización posible, puedes enviar un parche ;-))

Para array_diff, debería estar en ext/standard , lo que significa que, para PHP 5.3, debería estar allí: 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 revisando el código: es bastante largo ...)

Answer 6

Parece que puedes acelerar mucho más usando otra matriz en lugar de desarmarla. Sin embargo, esto utiliza más memoria, lo que podría ser un problema que depende del 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/