php array_intersect() eficiencia

Question

considere la siguiente secuencia de comandos. dos matrices con solo tres valores. Cuando comparo estas dos matrices usando array_intersect(). el resultado es rápido

<?php 
$arrayOne = array('3', '4', '5'); 
$arrayTwo = array('4', '5', '6'); 

$intersect = array_intersect($arrayOne, $arrayTwo); 

print_r($intersect); 

?> 

mi pregunta es cuál es la eficacia de array_intersect(). ya sea si comparamos dos matrices que tienen 1000 valores cada una. produciría un mejor resultado ..... r tenemos que usar alguna función hash para tratar de encontrar valores comunes rápidamente lo que será efectivo ??? .. necesito tu sugerencia para esto ...

estoy haciendo una aplicación.si una persona viene e inicia sesión utilizando Facebook login.then la aplicación obtendrá su lista de amigos y encontrar si algún amigo como se comentó en mi aplicación antes y mostrarle a él. aproximadamente unos amigos pueden tener entre 200 y 300 amigos en Facebook y DB tiene más de 1000 registros. Necesito encontrar eso de manera eficiente, ¿cómo puedo hacer eso .......

Answer 1

La intersección se puede implementar mediante la construcción de un conjunto de los valores buscados en la segunda matriz, y buscar en un conjunto se puede hacer tan rápido que se necesita un tiempo esencialmente constante en promedio. Por lo tanto, el tiempo de ejecución de todo el algoritmo puede estar en O(n).

Alternativamente, se puede ordenar la segunda matriz (en O(n log n)). Como la búsqueda en una matriz ordenada tiene un tiempo de ejecución en O(log n), todo el algoritmo debería tener un tiempo de ejecución en O(n log n).

De acuerdo con una prueba (corto, no científica) Acabo de funcionar, esto parece ser el caso de php de array_intersect:

Here's the code he usado para probarlo. Como puede ver, para un tamaño de entrada tan pequeño como 1000, no necesita preocuparse.

Answer 2

De lo que dice más arriba, le recomendaría implementar un mecanismo de almacenamiento en caché. De esa forma, cargaría el DB y aceleraría su aplicación. También te recomendaría que perfilaras la velocidad de array_intersect con una mayor cantidad de datos para ver cómo funciona la escala. Puede hacer esto simplemente envolviendo la llamada en llamadas para la hora del sistema y calcular la diferencia. Pero le recomendaría que use un generador de perfiles real para obtener buenos datos.

Answer 3

array_intersect ordena las matrices antes de comparar sus valores en paralelo (consulte el uso de zend_qsort en el source file array.c). Solo esto toma O (n · log n) para cada matriz. Entonces la intersección real solo toma tiempo lineal.

En función de los valores de las matrices, se podría aplicar esta intersección en el tiempo lineal y sin la clasificación, por ejemplo:

$index = array_flip($arrayOne); 
foreach ($arrayTwo as $value) { 
    if (isset($index[$value])) unset($index[$value]); 
} 
foreach ($index as $value => $key) { 
    unset($arrayOne[$key]); 
} 
var_dump($arrayOne); 

Answer 4

que la aplicación de este código simple de comparar array_intersect y array_intersect_key,

$array = array(); 
    for($i=0; $i<130000; $i++) 
     $array[$i] = $i; 
    for($i=200000; $i<230000; $i++) 
     $array[$i] = $i; 
    for($i=300000; $i<340000; $i++) 
     $array[$i] = $i; 

    $array2 = array(); 
    for($i=100000; $i<110000; $i++) 
     $array2[$i] = $i; 
    for($i=90000; $i<100000; $i++) 
     $array2[$i] = $i; 
    for($i=110000; $i<290000; $i++) 
     $array2[$i] = $i; 

    echo 'Intersect to arrays -> array1[' . count($array) . '] : array2[' . count($array2) . '] ' . '<br>'; 
    echo date('Y-m-d H:i:s') . '<br>'; 
    $time = time(); 
    $array_r2 = array_intersect_key($array,$array2); 
    echo 'Intercept key: ' . (time()-$time) . ' segs<br>'; 
    $time = time(); 
    $array_r = array_intersect($array,$array2); 
    echo 'Intercept: ' . (time()-$time) . ' segs<br>'; 

el resultado ....

Intersect to arrays -> array1[200000] : array2[200000] 
2014-10-30 08:52:52 
Intercept key: 0 segs 
Intercept: 4 segs 

I n esta comparación de la eficiencia entre array_intersect y array_intersect_key, podemos ver que la interceptación con claves es mucho más rápida.