Esistono strutture dati alternative rispetto agli array in PHP, dove posso beneficiare di diverse tecniche di indicizzazione?

Question

Ultimamente avevo un problema con un array che conteneva alcune centinaia di migliaia di valori e l'unica cosa che volevo fare era verificare se un valore era già presente. Nel mio caso si trattava di IP da un registro del server web. Quindi, in pratica qualcosa di simile:

in_array(ip2long(ip),$myarray) ha fatto il lavoro

Tuttavia, il tempo di ricerca è aumentato drammaticamente e 10k di ricerche ha preso circa 17 secondi o giù di lì.

Quindi in questo caso non mi importava se avessi duplicati o meno, avevo solo bisogno di verificare l'esistenza. Così ho potuto memorizzare gli indirizzi IP nell'indice come questo:

isset($myarray[ip2long($ip)]) 

e boom, i tempi di ricerca è andato giù da 17 secondi (e più) per un tempo statico di 0,8 secondi per 10k le ricerche. Come valore per la voce dell'array ho appena usato int 1.

Penso che l'indice di array sia probabilmente basato su un b-tree che dovrebbe avere log (n) tempo di ricerca e l'indice su una hashmap.

Nel mio caso, l'utilizzo dell'indice ha funzionato correttamente, ma esistono strutture di dati in cui è possibile utilizzare hashmaps come indice di valori, in cui possono essere utilizzati anche più valori (mi rendo conto che ciò ha senso solo se non si dispone di troppi duplicati e non posso usare efficientemente le richieste di intervallo/ricerca, che è il vantaggio principale delle strutture ad albero)?

Answer 1

ci sono tutta una serie di alternative Datastructures al di là di semplici matrici nel SPL library in bundle con PHP, tra cui le liste collegate, pile, mucchi, code, ecc

Tuttavia, ho il sospetto che potrebbe rendere il vostro logica un bel po ' più efficiente se si utilizza l'array flipped, consentendo di eseguire una ricerca sulla chiave (utilizzando la funzione array_key_exists()) anziché cercare il valore. L'indice dell'array è un hash, piuttosto che un btree, che rende molto veloce l'accesso diretto tramite la chiave.

Tuttavia, se si sta lavorando con le voci 10k in un array, è probabilmente meglio sfruttare un database, in cui è possibile definire i propri indici.

Answer 2

Gli array hanno un ordine sequenziale ed è rapido accedere a determinati elementi, perché non è necessario attraversare un albero o lavorare attraverso una struttura di elenchi sequenziale.

Un set è ovviamente più veloce qui, perché si controllano solo elementi univoci e non tutti gli elementi (nell'array).

Gli alberi vanno bene per esempio in strutture ordinate. È possibile implementare un albero con IP ordinati in base ai rispettivi intervalli, quindi è possibile decidere più rapidamente se questo IP esiste o meno. Non sono sicuro che PHP fornisca strutture ad albero personalizzate. Immagino che dovrai implementarlo da solo, ma ci vorrà circa mezz'ora.

Troverai codici di esempio sul web per tali strutture ad albero.

Answer 3

Hai anche l'estensione chdb (database hash costante), che è perfetto per questo.

Answer 4

come già risposto, è possibile utilizzare nuove classi fornite da spl http://www.php.net/spl

ma a quanto pare non sono veloce come la gente pensa. probabilmente non sono implementati come ci aspettiamo. E 'mia opinione che splfixedarray, per esempio, non è una vera e propria gamma, ma una tabella hash come array classico PHP

ma anche, avete alcune soluzioni alternative

prima è possibile memorizzare il risultato in un database. query sono veloci perché gli indici db possono essere meglio ottimizzato di un datastructure php

è possibile utilizzare http://www.php.net/sqlite3 e memorizzare i risultati in un database temporaneo (un file o in memoria)

suggerisco un file temporaneo, perché don' t necessario caricare tutto in memoria, e in più è possibile aggiungere ogni riga singolarmente (utilizzando http://www.php.net/fgets per esempio)

HTH!

si sentono liberi di correggere il mio inglese