Elenco di Big-O per funzioni PHP

Dopo aver usato PHP per un po 'di tempo, ho notato che non tutte le funzioni integrate di PHP sono veloci come previsto. Considera le seguenti due possibili implementazioni di una function che trova se un numero è primo usando un arrays di numbers primi memorizzati nella cache.

//very slow for large $prime_arrays $prime_arrays = arrays( 2, 3, 5, 7, 11, 13, .... 104729, ... ); $result_arrays = arrays(); foreach( $prime_arrays => $number ) { $result_arrays[$number] = in_arrays( $number, $large_prime_arrays ); } //speed is much less dependent on size of $prime_arrays, and runs much faster. $prime_arrays => arrays( 2 => NULL, 3 => NULL, 5 => NULL, 7 => NULL, 11 => NULL, 13 => NULL, .... 104729 => NULL, ... ); foreach( $prime_arrays => $number ) { $result_arrays[$number] = arrays_key_exists( $number, $large_prime_arrays ); } 

Questo perché in_arrays è implementato con una ricerca lineare O (n) che rallenta linearmente man $prime_arrays cresce $prime_arrays . Dove la function arrays_key_exists è implementata con una ricerca hash O (1) che non rallenterà a less che la tabella hash non venga popolata in modo estremo (nel qual caso è solo O (n)).

Finora ho dovuto scoprire i big-O tramite tentativi ed errori, e occasionalmente guardando il codice sorgente . Ora per la domanda …

C'è una list di tempi teorici (o pratici) di grandi size per tutte le funzioni PHP integrate?

* o alless quelli interessanti

Ad esempio, è molto difficile prevedere quale sia la grande O delle funzioni elencate perché la ansible implementazione dipende da strutture dati core sconosciute di PHP: arrays_merge, arrays_merge_recursive, arrays_reverse, arrays_intersect, arrays_combine, str_replace (con input di arrays), ecc.

Dal momento che non sembra che qualcuno abbia fatto questo prima ho pensato che sarebbe stata una buona idea averlo per riferimento da qualche parte. Sono andato però e sia tramite benchmark o code-skimming per caratterizzare le funzioni arrays_* . Ho provato a mettere il Big-O più interessante vicino alla cima. Questo elenco non è completo.

Nota: Tutto il Big-O where calcolato assumendo una ricerca hash è O (1) anche se è veramente O (n). Il coefficiente di n è così basso, il ram in testa di immagazzinare un arrays abbastanza grande ti farebbe male prima che le caratteristiche della ricerca Big-O inizino a prendere effetto. Ad esempio, la differenza tra una chiamata a arrays_key_exists a N = 1 e N = 1.000.000 è un aumento di tempo di ~ 50%.

Punti interessanti :

  1. isset / arrays_key_exists è molto più veloce di in_arrays e arrays_search
  2. + (unione) è un po 'più veloce di arrays_merge (e sembra più bello). Ma funziona in modo diverso quindi tienilo a mente.
  3. shuffle trova sullo stesso livello Big-O di arrays_rand
  4. arrays_pop / arrays_push è più veloce di arrays_shift / arrays_unshift causa della arrays_shift di arrays_shift

Ricerche :

arrays_key_exists O (n) ma molto vicino a O (1) – questo è dovuto al polling lineare nelle collisioni, ma poiché la probabilità di collisioni è molto piccola, anche il coefficiente è molto piccolo. Trovo che tratti le ricerche di hash come O (1) per dare un Big-O più realistico. Ad esempio il diverso tra N = 1000 e N = 100000 è solo di circa il 50% di rallentamento.

isset( $arrays[$index] ) O (n) ma molto vicino a O (1) – usa la stessa ricerca di arrays_key_exists. Dal momento che la costruzione del linguaggio, memorizzerà nella cache la ricerca se la chiave è hardcoded, risultando più veloce nei casi in cui la stessa chiave viene utilizzata ripetutamente.

in_arrays O (n) – questo perché fa una ricerca lineare attraverso l'arrays fino a quando non trova il valore.

arrays_search O (n) – usa la stessa function di base di in_arrays ma restituisce valore.

Funzioni di coda :

arrays_push O (Σ var_i, per tutti i)

arrays_pop O (1)

arrays_shift O (n) – deve reindicizzare tutte le chiavi

arrays_unshift O (n + Σ var_i, per tutti i) – deve reindicizzare tutte le chiavi

Intersezione di matrix, unione, sottrazione :

arrays_intersect_key se l'intersezione 100% fa O (Max (param_i_size) * Σparam_i_count, per tutti i), se l'intersezione 0% interseca O (Σparam_i_size, per tutti i)

arrays_intersect se l'intersezione 100% fa O (n ^ 2 * Σparam_i_count, per tutti i), se l'intersezione 0% interseca O (n ^ 2)

arrays_intersect_assoc se l'intersezione 100% fa O (Max (param_i_size) * Σparam_i_count, per tutti i), se l'intersezione 0% interseca O (Σparam_i_size, per tutti i)

arrays_diff O (π param_i_size, per tutti i) – Questo è il prodotto di tutti i param_sizes

arrays_diff_key O (Σ param_i_size, for i! = 1) – questo perché non è necessario eseguire iterazioni sul primo arrays.

arrays_merge O (Σ arrays_i, i! = 1) – non ha bisogno di scorrere il primo arrays

+ (unione) O (n), where n è la dimensione del secondo arrays (cioè arrays_first + arrays_second) – less overhead di arrays_merge poiché non deve rinumerare

arrays_replace O (Σ arrays_i, per tutti i)

Casuale :

shuffle O (n)

arrays_rand O (n) – Richiede un polling lineare.

Big-O ovvio :

arrays_fill O (n)

arrays_fill_keys O (n)

range O (n)

arrays_splice O (offset + lunghezza)

arrays_slice O (offset + length) o O (n) se length = NULL

arrays_keys O (n)

arrays_values O (n)

arrays_reverse O (n)

arrays_pad O (pad_size)

arrays_flip O (n)

arrays_sum O (n)

arrays_product O (n)

arrays_reduce O (n)

arrays_filter O (n)

arrays_map O (n)

arrays_chunk O (n)

arrays_combine O (n)

Vorrei ringraziare Eureqa per aver reso facile trovare il Big-O delle funzioni. È un fantastico programma gratuito che può trovare la migliore function adatta per dati arbitrari.

MODIFICARE:

Per coloro che dubitano che le ricerche di arrays PHP siano O(N) , ho scritto un benchmark per testarlo (sono ancora efficacemente O(1) per la maggior parte dei valori realistici).

grafico di ricerca di array php

 $tests = 1000000; $max = 5000001; for( $i = 1; $i <= $max; $i += 10000 ) { //create lookup arrays $arrays = arrays_fill( 0, $i, NULL ); //build test indexes $test_indexes = arrays(); for( $j = 0; $j < $tests; $j++ ) { $test_indexes[] = rand( 0, $i-1 ); } //benchmark arrays lookups $start = microtime( TRUE ); foreach( $test_indexes as $test_index ) { $value = $arrays[ $test_index ]; unset( $value ); } $stop = microtime( TRUE ); unset( $arrays, $test_indexes, $test_index ); printf( "%d,%1.15f\n", $i, $stop - $start ); //time per 1mil lookups unset( $stop, $start ); } 

La spiegazione per il caso specifico che descrivi è che gli arrays associativi sono implementati come tabelle hash – quindi la ricerca per chiave (e corrispondentemente, arrays_key_exists ) è O (1). Tuttavia, gli arrays non sono indicizzati in base al valore, quindi l'unico modo nel caso generale per scoprire se un valore esiste nell'arrays è una ricerca lineare. Non c'è nessuna sorpresa lì.

Non penso che ci sia una documentazione completa specifica della complessità algoritmica dei methods PHP. Tuttavia, se è una preoccupazione abbastanza grande da giustificare lo sforzo, puoi sempre consultare il codice sorgente .

Quasi sempre vuoi usare isset invece di arrays_key_exists . Non sto guardando gli interni, ma sono piuttosto sicuro che arrays_key_exists sia O (N) perché itera su each singolo tasto dell'arrays, mentre isset tenta di accedere all'elemento usando lo stesso algorithm di hash che viene usato quando si accede a un indice di arrays. Questo dovrebbe essere O (1).

Un "gotcha" a cui prestare attenzione è questo:

 $search_arrays = arrays('first' => null, 'second' => 4); // returns false isset($search_arrays['first']); // returns true arrays_key_exists('first', $search_arrays); 

Ero curioso, quindi ho confrontato la differenza:

 <?php $bigArray = range(1,100000); $iterations = 1000000; $start = microtime(true); while ($iterations--) { isset($bigArray[50000]); } echo 'is_set:', microtime(true) - $start, ' seconds', '<br>'; $iterations = 1000000; $start = microtime(true); while ($iterations--) { arrays_key_exists(50000, $bigArray); } echo 'arrays_key_exists:', microtime(true) - $start, ' seconds'; ?> 

is_set: 0.132308959961 secondi
arrays_key_exists: 2.33202195168 secondi

Naturalmente, questo non mostra la complessità del tempo, ma mostra come le 2 funzioni si confrontano l'una con l'altra.

Per verificare la complessità del tempo, confrontare la quantità di tempo necessaria per eseguire una di queste funzioni sulla prima chiave e sull'ultima chiave.

Se in pratica le persone si trovavano in difficoltà con le collisioni con le chiavi, implementavano i contenitori con una ricerca hash secondaria o tree bilanciato. L'tree bilanciato darebbe O (log n) comportmento peggiore e O (1) avg. caso (l'hash stesso). Il sovraccarico non vale la pena nella maggior parte delle applicazioni di memory pratiche, ma forse ci sono database che implementano questa forma di strategia mista come caso predefinito.