php array_intersect() efficienza

Question

considerare lo script seguente. due array con solo tre valori. Quando confronti questi due array usando array_intersect(). il risultato è veloce.

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

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

print_r($intersect); 

?> 

la mia domanda è qual è l'efficienza di array_intersect(). se confrontiamo due array con 1000 valori ciascuno. produrrebbe risultati migliori ..... r abbiamo bisogno di usare qualche funzione di hash per trattare con i valori comuni rapidamente che saranno efficaci ??? .. ho bisogno di un suggerimento per questo ...

sto facendo un application.if una persona viene ed effettua il login usando facebook login. dopodiché l'applicazione otterrà la sua lista amici e troverà se qualche amico ha già commentato nella mia app e glielo mostrerà. all'incirca un amico può avere tra 200 e 300 amici su facebook e db ha più di 1000 record. ho bisogno di trovarlo in modo efficiente come posso farlo .......

Answer 1

L'intersezione può essere implementata costruendo un insieme di valori cercati nel secondo array, e cercare in un set può essere fatto così velocemente che richiede in media tempo sostanzialmente costante. Pertanto, il tempo di esecuzione dell'intero algoritmo può essere O(n).

In alternativa, è possibile ordinare il secondo array (in O(n log n)). Poiché la ricerca in una matrice ordinata ha un runtime in O(log n), l'intero algoritmo dovrebbe quindi avere un runtime in O(n log n).

Secondo un test (breve, non scientifica) Ho appena eseguito, questo sembra essere il caso per php di array_intersect:

Here's the code ho usato per testarlo. Come puoi vedere, per un'input di dimensioni pari a 1000, non devi preoccuparti.

Answer 2

Da quanto dichiarato in precedenza, ti consiglierei di implementare un meccanismo di memorizzazione nella cache. In questo modo dovresti caricare il DB e accelerare la tua applicazione. Ti suggerisco inoltre di definire la velocità di array_intersect con una quantità crescente di dati per vedere come scala le prestazioni. È possibile farlo semplicemente avvolgendo la chiamata in chiamate per l'ora di sistema e calcolare la differenza. Ma ti consiglio di utilizzare un vero profiler per ottenere buoni dati.

Answer 3

array_intersect ordina gli array prima di confrontare i loro valori in parallelo (vedere l'uso di zend_qsort in source file array.c). Questo da solo prende O (n · log n) per ciascun array. Quindi l'intersezione effettiva richiede solo un tempo lineare.

A seconda dei valori negli array, è possibile implementare questo incrocio nel tempo lineare, senza l'ordinamento, ad esempio:

$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

ho attuare questo semplice codice di confronto tra array_intersect e 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>'; 

il risultato ....

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

I n questo confronto dell'efficienza tra array_intersect e array_intersect_key, possiamo vedere l'intercettazione con le chiavi che è molto più veloce.