Algoritmi di ricerca

di Piero Giuseppe Goletto

La ragione fondamentale per effettuare l’ordinamento di un insieme di dati è poter effettuare ricerche al suo interno. In questo articolo esamineremo i due algoritmi più semplici, supponendo di avere un archivio di coppie numero-nome: è quello che succede, per esempio, nelle gare sportive.

Diremo ad esempio che la chiave è il numero di gara e il valore è il nome del concorrente: nel caso della F1, abbiamo 5 – Vettel, 7 – Raikkonen, 44 – Hamilton. Il più semplice metodo per effettuare una ricerca è analogo a quello che adoperiamo noi esseri umani nel momento in cui dobbiamo reperire un elemento di un breve elenco (“breve” quanto? Facciamo fino ad un foglio A4, quindi 50 elementi): lo scorriamo.

Questa tecnica si chiama “ricerca sequenziale”: si parte dall’elemento n° 1, e si procede sino a quando l’elemento in esame è uguale a quello che ci interessa. Se cerchiamo il numero 44, possiamo arrivare a dover scorrere fino a tutti i 43 elementi precedenti per raggiungere il valore Lewis Hamilton.

Una tecnica di ricerca alternativa invece si basa sul concetto di “ricerca dicotomica” o di “ricerca binaria”. Questa si usa per esempio partendo da un insieme molto grande di dati ordinati (quanto “grande”? per esempio, centomila elementi). Poiché la quantità degli elementi in ingresso è variabile l’applicazione, all’atto del caricamento dei dati, ne ha determinato il numero. In questo esempio ipotizzeremo di dover impostare la gestione di un supermercato e che la ricerca debba essere effettuata su un file che contiene 100.000 codici di magazzino, composto di coppie codice – descrizione e, per semplicità, supporremo che questo file venga caricato in memoria, che le chiavi siano tutti i numeri interi compresi tra 1 e 100.000 e di voler cercare l’elemento avente chiave 62.500.

 

1                                  Latte intero

2                                  Latte scremanto

50.000                        Sapone da barba

50.001                        Dopobarba

62.500                        Olio d’Oliva

75.000                        Aceto balsamico Modena

99.999                        Buste

100.000                     Quaderni

 Si procede così: si individua l’elemento centrale dell’archivio (la cui chiave è 50.000); si confronta il valore della chiave con quello della chiave cercata. Se il valore della chiave trovata è minore della chiave cercata, si procede con un nuovo tentativo nella prima metà dell’archivio altrimenti, come è il nostro caso, si procede nel secondo segmento. Noi cerchiamo l’elemento 62.500 che non è l’elemento n. 50.000. Si tenta pertanto con una chiave pari a 50.000 più la metà delle restanti, quindi si prova con 75.000. Dato che il valore della chiave cercata è inferiore a questo valore, si effettua una nuova ricerca tra 50.000 e 75.000 puntando esattamente a metà: 62.500 e qui si interrompe la nostra ricerca perché abbiamo trovato il valore che cercavamo, che in base alla tabella prima citata è l’Olio d’Oliva. Più spesso archivi così grandi sono memorizzati su disco con file ad accesso diretto. Un file ad accesso diretto consente di spostarsi all’interno dell’archivio per reperire l’informazione cercata. La soluzione più semplice per ottenere questo risultato è dotare ciascun archivio dati di un indic

e che è, a tutti gli effetti, un indice analitico. E’ questo indice ad essere caricato in memoria.

 Nella tabella riportata di seguito i valori in fondino azzurro sono quelli che vengono caricati in memoria. Nella colonna centrale è riportata la posizione di ciascun elemento, contando che ciascuna riga occupi 64 caratteri; la ricerca restituisce la posizione in cui reperire gli elementi da disco.

 

CHIAVE POSIZIONE SU DISCO DESCRIZIONE

 

1                                  1                                 Latte intero

25.000                        1.600.000                  Uva da tavola

50.000                        3.200.000                  Sapone da barba

60.000                        3.840.000                  Cibo per gatti

62.500                        4.000.000                  Olio d’Oliva

75.000                        4.800.000                  Aceto balsamico Modena

100.000                     6.400.000                  Quaderni

 

Il vantaggio di disporre di un indice sta nel fatto che solitamente la ricerca tramite indice risulta molto più veloce perché richiede meno passaggi. Si tenga conto che possono essere realizzati indici a più livelli, se occorre trattare archivi con moltissimi dati. Per esempio, a fronte di archivi con milioni di elementi, avrebbe senso creare un indice di terzo livello che punta di diecimila elementi in diecimila elementi; un indice di secondo livello che, per ciascun blocco di diecimila elementi, punta a ogni elemento rappresentativo delle migliaia; un indice di terzo livello che per ciascun blocco di mille elementi restituisce la posizione di ogni “centesimo” elemento. Tutto ciò ha lo scopo di sveltire la ricerca e ci introduce all’argomento del prossimo articolo, che introdurrà una struttura importantissima: gli alberi di ricerca.