Ho già pubblicato una lezione di base sugli array in PHP, dedicata in particolare ai web developers o agli smanettoni che non hanno solide basi di programmazione. Vediamo qui come implementare gli algoritmi di ricerca di un elemento all’interno di un vettore. Useremo PHP perchè è molto diffuso, ma in realtà, per varie ragioni, questi algoritmi risultano molto più utili se implementati in altri linguaggi.
Ricerca sequenziale semplice
Questo algoritmo è semplicissimo. Il procedimento consiste nello scorrere tutti gli elementi dell’array dal primo all’ultimo, fino a quando si trova quello desiderato o fino a quando si giunge alla fine.
function seq_search($needle, $haystack, $start=0, $end=null)
{
if (is_null($end))
$end = count($haystack);
for ($i=$start; $i <= $end; $i++)
if ($haystack[$i]==$needle)
return $i;
return null;
}
Nell’esempio, si effettua un ciclo in cui si scorrono tutti gli elementi. Ogni volta viene controllato l’elemento corrente, per sapere se corrisponde a quello cercato. Se viene trovato, si restituisce il suo indice, uscendo dalla funzione. Se non viene trovato, si termina il ciclo e si restituisce null.
Anche se di solito non viene fatto, ho scelto di implementare due parametri opzionali: $start e $end. Per default $start corrisponde a 0 (il primo elemento del vettore) e $end corrisponde all’indice dell’ultimo elemento (il numero degli elementi-1, visto che il conteggio inizia da 0). Detto questo, se sappiamo che l’elemento desiderato si trova, poniamo, dopo l’elemento 20 e prima dell’elemento 30, è possibile rendere la ricerca più breve specificando i .
Ricerca sequenziale su array ordinati
L’algoritmo sopra esposto non comprende nessun tipo di ottimizzazione. Se si cerca un elemento inesistente in un array di mille elementi, vengono eseguiti mille cicli. Se però sappiamo che l’array con il quale stiamo lavorando è ordinato (dall’elemento più basso a quello più alto) è possibile implementare qualche ottimizzazione.
function ord_search($needle, $haystack, $start=0, $end=null)
{
if (is_null($end))
$end = count($haystack);
for ($i=$start; $haystack[$i] <= $needle && $i <= $end; $i++)
if ($haystack[$i]==$needle)
return $i;
return null;
}
In questa variante, per ogni elemento si controlla non solo se esso è quello desiderato, ma anche se è minore. Nel caso sia maggiore, significa che l’elemento da noi desiderato non è presente nell’array.
Ricerca sequenziale con sentinella
L’algoritmo precedente presenta un problema: ad ogni ciclo vengono eseguiti due controlli. Questo significa che, se l’elemento che cerchiamo è maggiore di tutti quelli presenti nell’array, non abbiamo ottimizzato proprio nulla, anzi abbiamo aumentato il carico di lavoro.
E’ più efficiente, quindi, la ricerca con sentinella. Essa consiste nel porre l’elemento desiderato in coda all’array e poi, ad ogni ciclo, controllare semplicemente se l’elemento corrente è quello desiderato. Se lo è, controlleremo se è anche l’ultimo elemento; in tal caso è quello che abbiamo aggiunto noi, di conseguenza nell’array originale l’elemento non c’era. Altrimenti verrà trovato l’elemento originale.
function sen_search($needle, $haystack)
{
$sentry = count($haystack);
$haystack[$sentry] = $needle;
for ($i=$start; true; $i++)
if ($haystack[$i]==$needle)
if ($i==$sentry)
return null;
else
return $i;
}
Ricerca binaria (o dicotomica)
La ricerca binaria è in un certo senso abbastanza “umano”. Quando noi cerchiamo una parola sul dizionario non effettuiamo una ricerca sequenziale, ma dicotomica. Ossia: apriamo il dizionario a un certo punto, se la parola che cerchiamo si trova più avanti lo apriamo più avanti tenendo il vecchio segno, se siamo andati troppo avanti torniamo indietro…
Formalizzato, funziona così: ricordiamo due indici, che sono i due estremi della nostra ricerca: $low e $high.Inizialmente questi indici corrispondono al primo elemento dell’array e all’ultimo. Da questi calcoliamo la metà: $mid = ($low + $high) / 2. Controlliamo se l’elemento che corrisponde a $mid è quello che cerchiamo. Se lo è, la ricerca è terminata. Se invece $mid è minore dell’elemento che cerchiamo, sposteremo $low nel punto in cui si trova $mid; se invece è maggiore, sposteremo $high dove si trova $mid. A questo punto ricominceremo daccapo ricalcolando il nuovo valore di $mid. E così via finchè troveremo l’elemento che cerchiamo o, se manca, fino a quando $low sarà maggior di $high.
function bin_search($needle, $haystack, $low=0, $high=null)
{
// default last value
if (is_null($high))
$high = count($haystack) - 1;
// search
while ($low <= $high) {
$mid = floor(($low + $high) / 2);
if ($haystack[$mid]==$needle)
// found; return current position
return $mid;
if ($haystack[$mid] < $needle)
// search in higher values
$low = $mid + 1;
else
// search in lower values
$high = $mid - 1;
}
// not found
return null;
}
Varianti
La ricerca sequenziale ha un’utile variante: la ricerca sequenziale inversa. Sebbene nella maggior parte dei casi sia indifferente utilizzare l’una o l’altra, in alcuni casi potremmo sapere che l’elemento desiderato si trova verso la fine dell’array, e non verso l’inizio. In questo caso la ricerca sequenziale inversa risulta migliore, in quanto probabilmente effettuerà meno cicli. Inoltre, se non si utilizzano i parametri $start e $end, la ricerca inversa comporta l’uso di una variabile in meno rispetto a quella ordinaria (perchè l’ultimo elemento sarà sempre 0, mentre in una ricerca normale varia a seconda della lunghezza dell’array e quindi deve essere calcolato).
Per quanto riguarda PHP…
PHP comprende una funzione nativa per ricercare un elemento in array: in_array(). Dunque, come si diceva all’inizio, PHP è stato utilizzato come linguaggio per gli esempi perchè è molto diffuso, non perchè questi algoritmi siano particolarmente utili in PHP.
Va comunque detto che in_array() effettua una ricerca sequenziale su array che si suppone non siano ordinati. Nel caso l’array con cui si sta lavorando sia ordinato e di grosse dimensioni, è probabile che una ricerca binaria implementata in PHP - per quanto non particolarmente performante - risulterà comunque un’utile ottimizzazione.
L’ideale sarebbe comunque implementare la ricerca binaria in C come modulo per PHP, soluzione che però ci è negata se non possiamo amministrare il server sul quale gli script verranno eseguiti.