Ricerca binaria in array

[ligamarco]

Ciao.
Devo controllare se una certa stringa appartiene ad un elemento di un array. Per questo ho visto che esiste la funzione PHP "in_array" che restituisce TRUE se trova l'elemento e FALSE altrimenti. Siccome il mio array contiene più di 60.000 elementi e devo fare diversi confronti, volevo sapere se questa funzione utilizzasse la ricerca binaria (detta anche dicotomica) oppure se esistesse un'altra funzione PHP che eseguisse questa ricerca.

Grazie.
Ciao.

[skidx]

certamente no, visto che la funzione non sa se il tuo array è ordinato.

In linea di massima le funzioni native del PHP sono più veloci della corrispondente funzione riscritta in PHP, in quanto compilate, però per casi limite potresti ottenere risultati migliori con del codice PHP ottimizzato per la tua esigenza.

Fai una prova e vedi in che modo fai prima.

[ligamarco]

Grazie per avermi risposto.
Sai se esiste una funzione nativa di PHP per la ricerca binaria su un array ordinato???

Nella documentazione della funzione in_array c'è questa nota di un utente:

To look through a large array, it is much more efficient when it is sorted to use a binary chop method, so that the number of calls is equal to log(number_of_values_in_array) / log2 rather than equal to the number of values in the array.

For a million values in an array, it can therefore return whether this index exists in a file using no more than 20 calls to the array rather than a million. This makes it 50,000 times more efficient for an array of this size. I'm sure you can imagine what a million calls can do to a processor, and it isn't nice.

Hope this helps someone.

[skidx]

Originariamente inviato da ligamarco
Sai se esiste una funzione nativa di PHP per la ricerca binaria su un array ordinato???

Che io sappia no, comunque ti ripeto, a scriverla fai in fretta, son 3 righe, poi fai dei test e vedi se nel tuo caso specifico è più performante in_array() o la tua funzione di ricerca binaria.

[ligamarco]

Grazie della risposta...
Beh, ho fatto una prova ed è decisamente più performante la ricerca binaria...però ho un problema:
in sostanza io dovrei fare la ricerca in un dizionario, quindi ho 2 array, uno ottenuto dalla lettura di un file txt con tutte le parole del dizionario ed un altro con le parole del testo da confrontare. Ho constatato che con la ricerca binaria si ottiene un confronto più veloce, ma le parole riconosciute sono decisamente minori (rispetto all'uso della funzione in_array) non riesco a capirne il motivo dove posso trovare il sorgente della funzione in_array? Così controllo se usa qualche funzione particolare per la formattazione del testo...

Grazie.
Ciao