Introduzione

La ricerca di dati memorizzati in diverse strutture di dati è una parte cruciale di quasi ogni singola applicazione.

Ci sono molti algoritmi diversi disponibili per la ricerca, e ognuno ha diverse implementazioni e si basa su diverse strutture di dati per fare il lavoro.

Essere in grado di scegliere un algoritmo specifico per un dato compito è un’abilità chiave per gli sviluppatori e può fare la differenza tra un’applicazione veloce, affidabile e stabile e un’applicazione che si sgretola per una semplice richiesta.

• Operatori di appartenenza
• Ricerca lineare
• Ricerca binaria
• Ricerca a salti
• Ricerca Fibonacci
• Ricerca esponenziale
• Ricerca interpolazione

Operatori di associazione

Gli algoritmi si sviluppano e si ottimizzano nel tempo come risultato di una costante evoluzione e della necessità di trovare le soluzioni più efficienti per problemi sottostanti in diversi domini.

Uno dei problemi più comuni nel dominio dell’informatica è la ricerca attraverso una collezione e determinare se un dato oggetto è presente o meno nella collezione.

Quasi ogni linguaggio di programmazione ha la sua implementazione di un algoritmo di ricerca di base, di solito come una funzione che restituisce un valore Boolean di True o False quando un oggetto viene trovato in una data collezione di oggetti.

In Python, il modo più semplice per cercare un oggetto è usare gli operatori di appartenenza – chiamati così perché ci permettono di determinare se un dato oggetto è un membro di una collezione.

Questi operatori possono essere usati con qualsiasi struttura dati iterabile in Python, incluse stringhe, liste e tuple.

• in – Restituisce True se l’elemento dato fa parte della struttura.
• not in – Restituisce True se l’elemento dato non fa parte della struttura.

>>> 'apple' in True>>> 't' in 'stackabuse'True>>> 'q' in 'stackabuse'False>>> 'q' not in 'stackabuse'True

Gli operatori di appartenenza sono sufficienti quando tutto ciò che dobbiamo fare è trovare se esiste una sottostringa in una data stringa, o determinare se due stringhe, liste o tuple si intersecano in termini di oggetti che contengono.

Nella maggior parte dei casi abbiamo bisogno della posizione dell’elemento nella sequenza, oltre a determinare se esiste o meno; gli operatori di appartenenza non soddisfano questo requisito.

Ci sono molti algoritmi di ricerca che non dipendono dagli operatori integrati e possono essere usati per cercare valori più velocemente e/o in modo più efficiente. Inoltre, possono fornire più informazioni, come la posizione dell’elemento nell’insieme, piuttosto che essere in grado di determinare solo la sua esistenza.

Ricerca lineare

La ricerca lineare è uno degli algoritmi di ricerca più semplici e più facili da capire. Possiamo pensarlo come una versione potenziata della nostra implementazione dell’operatore in di Python.

L’algoritmo consiste nell’iterare su un array e restituire l’indice della prima occorrenza di un elemento una volta trovato:

def LinearSearch(lys, element): for i in range (len(lys)): if lys == element: return i return -1

Quindi se usiamo la funzione per calcolare:

>>> print(LinearSearch(, 2))

Eseguendo il codice, siamo accolti con:

1

Questo è l’indice della prima occorrenza dell’elemento che stiamo cercando – tenendo presente che gli indici Python sono basati su 0.

La complessità temporale della ricerca lineare è O(n), il che significa che il tempo di esecuzione aumenta con il numero di elementi nella nostra lista di input lys.

La ricerca lineare non è spesso usata nella pratica, perché la stessa efficienza può essere raggiunta usando metodi incorporati o operatori esistenti, e non è così veloce o efficiente come altri algoritmi di ricerca.

La ricerca lineare è una buona soluzione per quando abbiamo bisogno di trovare la prima occorrenza di un elemento in una collezione non ordinata perché, a differenza della maggior parte degli altri algoritmi di ricerca, non richiede che una collezione sia ordinata prima di iniziare la ricerca.

Ricerca binaria

La ricerca binaria segue una metodologia divide et impera. È più veloce della ricerca lineare ma richiede che l’array sia ordinato prima che l’algoritmo venga eseguito.

Assumendo che stiamo cercando un valore val in un array ordinato, l’algoritmo confronta val con il valore dell’elemento centrale dell’array, che chiameremo mid.

• Se mid è l’elemento che stiamo cercando (caso migliore), restituiamo il suo indice.
• Se no, identifichiamo su quale lato di mid val è più probabile che si trovi in base al fatto che val sia più piccolo o più grande di mid, e scartiamo l’altro lato dell’array.
• Poi ricorsivamente o iterativamente seguiamo gli stessi passi, scegliendo un nuovo valore per mid, confrontandolo con val e scartando la metà delle possibili corrispondenze in ogni iterazione dell’algoritmo.

L’algoritmo di ricerca binaria può essere scritto sia ricorsivamente che iterativamente. La ricorsione è generalmente più lenta in Python perché richiede l’allocazione di nuovi stack frame.

Siccome un buon algoritmo di ricerca dovrebbe essere il più veloce e accurato possibile, consideriamo l’implementazione iterativa della ricerca binaria:

Se usiamo la funzione per calcolare:

>>> BinarySearch(, 20)

otteniamo il risultato:

1

che è l’indice del valore che stiamo cercando.

L’azione che l’algoritmo esegue dopo in ogni iterazione è una delle diverse possibilità:

• Ritorna l’indice dell’elemento corrente
• Ricerca attraverso la metà sinistra dell’array
• Ricerca attraverso la metà destra dell’array

Possiamo scegliere solo una possibilità per iterazione, e il nostro pool di possibili corrispondenze viene diviso per due in ogni iterazione. Questo rende la complessità temporale della ricerca binaria O(log n).

Un inconveniente della ricerca binaria è che se ci sono più occorrenze di un elemento nell’array, non restituisce l’indice del primo elemento, ma piuttosto l’indice dell’elemento più vicino al centro:

>>> print(BinarySearch(, 4))

Eseguendo questo pezzo di codice si otterrà l’indice dell’elemento centrale:

1

Per confronto, eseguendo una ricerca lineare sullo stesso array si otterrà:

0

Che è l’indice del primo elemento. Tuttavia, non possiamo categoricamente dire che la ricerca binaria non funziona se una matrice contiene lo stesso elemento due volte – può funzionare proprio come la ricerca lineare e restituire la prima occorrenza dell’elemento in alcuni casi.

Se eseguiamo la ricerca binaria sulla matrice per esempio, e cerchiamo 4, otterremo 3 come risultato.

La ricerca binaria è abbastanza usata in pratica perché è efficiente e veloce rispetto alla ricerca lineare. Tuttavia, ha alcuni difetti, come la sua dipendenza dall’operatore //. Ci sono molti altri algoritmi di ricerca divide et impera che sono derivati dalla ricerca binaria, esaminiamone alcuni.

Ricerca a salti

La ricerca a salti è simile alla ricerca binaria in quanto lavora su un array ordinato, e usa un simile approccio divide et impera per cercare attraverso di esso.

Può essere classificata come un miglioramento dell’algoritmo di ricerca lineare poiché dipende dalla ricerca lineare per eseguire il confronto effettivo quando si cerca un valore.

Dato un array ordinato, invece di cercare attraverso gli elementi dell’array in modo incrementale, cerchiamo in salti. Così nella nostra lista di input lys, se abbiamo una dimensione di salto di salto il nostro algoritmo considererà gli elementi nell’ordine lys, lys, lys, lys e così via.

Con ogni salto, memorizziamo il valore precedente che abbiamo guardato e il suo indice. Quando troviamo un insieme di valori dove lys<elemento<lys, eseguiamo una ricerca lineare con lys come elemento più a sinistra e lys come elemento più a destra nel nostro insieme di ricerca:

Siccome questo è un algoritmo complesso, consideriamo il calcolo passo per passo della ricerca a salti con questo input:

>>> print(JumpSearch(, 5))

• La ricerca a salti determina prima la dimensione del salto calcolando math.sqrt(len(lys)). Poiché abbiamo 9 elementi, la dimensione del salto sarebbe √9 = 3.
• Poi, calcoliamo il valore della variabile right, che è il minimo della lunghezza dell’array meno 1, o il valore di left+jump, che nel nostro caso sarebbe 0+3= 3. Poiché 3 è più piccolo di 8, usiamo 3 come valore di right.
• Ora controlliamo se il nostro elemento di ricerca, 5, è tra lys e lys. Poiché 5 non è tra 1 e 4, andiamo avanti.
• Poi, facciamo di nuovo i calcoli e controlliamo se il nostro elemento di ricerca è tra lys e lys, dove 6 è 3+salto. Poiché 5 è tra 4 e 7, facciamo una ricerca lineare sugli elementi tra lys e lys e restituiamo l’indice del nostro elemento come:

4

La complessità temporale della ricerca con salto è O(√n), dove √n è la dimensione del salto, e n è la lunghezza della lista, ponendo la ricerca con salto tra la ricerca lineare e gli algoritmi di ricerca binaria in termini di efficienza.

Il vantaggio più importante della ricerca a salti rispetto alla ricerca binaria è che non si basa sull’operatore di divisione (/).

Nella maggior parte delle CPU, usare l’operatore di divisione è costoso rispetto alle altre operazioni aritmetiche di base (addizione, sottrazione e moltiplicazione), perché l’implementazione dell’algoritmo di divisione è iterativa.

Il costo di per sé è molto piccolo, ma quando il numero di elementi da cercare è molto grande, e il numero di operazioni di divisione che dobbiamo eseguire aumenta, il costo può sommarsi in modo incrementale. Perciò la ricerca a salti è migliore della ricerca binaria quando c’è un gran numero di elementi in un sistema in cui anche un piccolo aumento di velocità conta.

Per rendere la ricerca a salti più veloce, potremmo usare la ricerca binaria o un’altra ricerca a salti interna per cercare attraverso i blocchi, invece di affidarci alla ricerca lineare molto più lenta.

Ricerca di Fibonacci

La ricerca di Fibonacci è un altro algoritmo divide et impera che ha delle somiglianze sia con la ricerca binaria che con quella a salti. Prende il suo nome perché usa i numeri di Fibonacci per calcolare la dimensione del blocco o l’intervallo di ricerca in ogni passo.

I numeri di Fibonacci iniziano con zero e seguono lo schema 0, 1, 1, 2, 3, 5, 8, 13, 21… dove ogni elemento è la somma dei due numeri che lo precedono immediatamente.

L’algoritmo lavora con tre numeri di Fibonacci alla volta. Chiamiamo i tre numeri fibM, fibM_minus_1 e fibM_minus_2 dove fibM_minus_1 e fibM_minus_2 sono i due numeri immediatamente precedenti a fibM nella sequenza:

fibM = fibM_minus_1 + fibM_minus_2

Inizializziamo i valori a 0,1 e 1 o i primi tre numeri della sequenza di Fibonacci per evitare un errore di indice nel caso in cui il nostro array di ricerca lys contiene un numero molto piccolo di elementi.

Poi scegliamo il numero più piccolo della sequenza di Fibonacci che è maggiore o uguale al numero di elementi del nostro array di ricerca lys, come valore di fibM, e i due numeri di Fibonacci immediatamente precedenti come valori di fibM_minus_1 e fibM_minus_2. Mentre l’array ha ancora elementi e il valore di fibM è maggiore di uno, noi:

• Confrontiamo val con il valore del blocco nell’intervallo fino a fibM_minus_2, e restituiamo l’indice dell’elemento se corrisponde.
• Se il valore è maggiore dell’elemento che stiamo guardando, spostiamo i valori di fibM, fibM_minus_1 e fibM_minus_2 due passi in basso nella sequenza di Fibonacci, e reimpostiamo l’indice all’indice dell’elemento.
• Se il valore è minore dell’elemento che stiamo guardando, spostiamo i valori di fibM, fibM_minus_1 e fibM_minus_2 un passo in basso nella sequenza di Fibonacci.

Diamo un’occhiata all’implementazione Python di questo algoritmo:

Se usiamo la funzione FibonacciSearch per calcolare:

>>> print(FibonacciSearch(, 6))

Diamo un’occhiata al processo passo dopo passo di questa ricerca:

• Determinare il più piccolo numero di Fibonacci maggiore o uguale alla lunghezza della lista come fibM; in questo caso, il più piccolo numero di Fibonacci che soddisfa i nostri requisiti è 13.
• I valori sarebbero assegnati come:
  • fibM = 13
  • fibM_minus_1 = 8
  • fibM_minus_2 = 5
  • index = -1
• In seguito, controlliamo l’elemento lys dove 4 è il minimo di -1+5 . Poiché il valore di lys è 5, che è più piccolo del valore che stiamo cercando, spostiamo i numeri di Fibonacci un passo in basso nella sequenza, rendendo i valori:
  • fibM = 8
  • fibM_minus_1 = 5
  • fibM_minus_2 = 3
  • indice = 4
• In seguito, controlliamo l’elemento lys dove 7 è il minimo di 4+3. Poiché il valore di lys è 8, che è maggiore del valore che stiamo cercando, spostiamo i numeri di Fibonacci due passi in basso nella sequenza.
  • fibM = 3
  • fibM_minus_1 = 2
  • fibM_minus_2 = 1
  • indice = 4
• Ora controlliamo l’elemento lys dove 5 è il minimo di 4+1 . Il valore di lys è 6, che è il valore che stiamo cercando!

Il risultato, come previsto è:

5

La complessità temporale della ricerca di Fibonacci è O(log n); la stessa della ricerca binaria. Questo significa che l’algoritmo è più veloce sia della ricerca lineare che della ricerca a salti nella maggior parte dei casi.

La ricerca di Fibonacci può essere usata quando abbiamo un numero molto grande di elementi da cercare, e vogliamo ridurre l’inefficienza associata all’uso di un algoritmo che si basa sull’operatore di divisione.

Un ulteriore vantaggio dell’uso della ricerca di Fibonacci è che può ospitare array di input che sono troppo grandi per essere tenuti nella cache della CPU o nella RAM, perché cerca tra gli elementi in passi crescenti, e non in una dimensione fissa.

Ricerca esponenziale

La ricerca esponenziale è un altro algoritmo di ricerca che può essere implementato abbastanza semplicemente in Python, rispetto alla ricerca con salto e alla ricerca di Fibonacci che sono entrambi un po’ complessi. È anche conosciuto con i nomi di ricerca al galoppo, ricerca al raddoppio e ricerca di Struzik.

La ricerca esponenziale dipende dalla ricerca binaria per eseguire il confronto finale dei valori. L’algoritmo funziona:

• Determinando l’intervallo in cui è probabile che l’elemento che stiamo cercando sia
• Utilizzando la ricerca binaria per l’intervallo per trovare l’indice esatto dell’elemento

L’implementazione Python dell’algoritmo di ricerca esponenziale è:

Se usiamo la funzione per trovare il valore di:

>>> print(ExponentialSearch(,3))

L’algoritmo funziona così:

• Controllando se il primo elemento della lista corrisponde al valore che stiamo cercando – poiché lys è 1 e stiamo cercando 3, impostiamo l’indice a 1 e andiamo avanti.
• Passiamo attraverso tutti gli elementi della lista, e mentre l’elemento alla posizione dell’indice è minore o uguale al nostro valore, aumentiamo esponenzialmente il valore di index in multipli di due:
  • indice = 1, lys è 2, che è meno di 3, quindi l’indice è moltiplicato per 2 e impostato su 2.
  • indice = 2, lysè 3, che è uguale a 3, quindi l’indice è moltiplicato per 2 e impostato su 4.
  • indice = 4, lysè 5, che è maggiore di 3; il ciclo viene interrotto a questo punto.
• Esegue una ricerca binaria affettando la lista; arr. In Python, questo significa che la sottoelenco conterrà tutti gli elementi fino al quarto elemento, quindi in realtà stiamo chiamando:

>>> BinarySearch(, 3)

che restituirà:

2

che è l’indice dell’elemento che stiamo cercando sia nella lista originale, sia nella lista affettata che passiamo all’algoritmo di ricerca binaria.

La ricerca esponenziale funziona in tempo O(log i), dove i è l’indice dell’elemento che stiamo cercando. Nel suo caso peggiore, la complessità temporale è O(log n), quando l’ultimo elemento è l’elemento che stiamo cercando (n è la lunghezza dell’array).

La ricerca esponenziale funziona meglio della ricerca binaria quando l’elemento che stiamo cercando è più vicino all’inizio dell’array. In pratica, usiamo la ricerca esponenziale perché è uno degli algoritmi di ricerca più efficienti per le matrici non limitate o infinite.

Ricerca per interpolazione

La ricerca per interpolazione è un altro algoritmo divide et impera, simile alla ricerca binaria. A differenza della ricerca binaria, non inizia sempre la ricerca al centro. La ricerca per interpolazione calcola la probabile posizione dell’elemento che stiamo cercando usando la formula:

index = low + )*(high-low) / (lys-lys)]

dove le variabili sono:

• lys – il nostro array di input
• val – l’elemento che stiamo cercando
• index – il probabile indice dell’elemento cercato. Questo è calcolato per essere un valore più alto quando val è più vicino in valore all’elemento alla fine dell’array (lys), e più basso quando val è più vicino in valore all’elemento all’inizio dell’array (lys)
• low – l’indice iniziale dell’array
• high – l’ultimo indice dell’array

L’algoritmo cerca calcolando il valore di index:

• Se viene trovata una corrispondenza (quando lys == val), l’indice viene restituito
• Se il valore di val è inferiore a lys, il valore per l’indice viene ricalcolato usando la formula per la sotto-array sinistra
• Se il valore di val è maggiore di lys, il valore dell’indice viene ricalcolato usando la formula per la sotto-array di destra

Andiamo avanti e implementiamo la ricerca per interpolazione usando Python:

Se usiamo la funzione per calcolare:

>>> print(InterpolationSearch(, 6))

I nostri valori iniziali sarebbero:

• val = 6,
• low = 0,
• high = 7,
• lys = 1,
• lys = 8,
• index = 0 + = 5

Siccome lys è 6, che è il valore che stiamo cercando, fermiamo l’esecuzione e restituiamo il risultato:

5

Se abbiamo un gran numero di elementi, e il nostro indice non può essere calcolato in una sola iterazione, continuiamo a ricalcolare i valori dell’indice dopo aver regolato i valori di alto e basso nella nostra formula.

La complessità temporale della ricerca per interpolazione è O(log log n) quando i valori sono distribuiti uniformemente. Se i valori non sono uniformemente distribuiti, la complessità temporale nel caso peggiore è O(n), la stessa della ricerca lineare.

La ricerca per interpolazione funziona meglio su array uniformemente distribuiti e ordinati. Mentre la ricerca binaria parte dal centro e si divide sempre in due, la ricerca per interpolazione calcola la probabile posizione dell’elemento e controlla l’indice, rendendo più probabile trovare l’elemento in un minor numero di iterazioni.

Perché usare Python per la ricerca?

Python è altamente leggibile ed efficiente rispetto ai vecchi linguaggi di programmazione come Java, Fortran, C, C++ ecc. Un vantaggio chiave dell’uso di Python per implementare algoritmi di ricerca è che non ci si deve preoccupare del casting o della digitazione esplicita.

In Python, la maggior parte degli algoritmi di ricerca che abbiamo discusso funzioneranno altrettanto bene se stiamo cercando una stringa. Tenete a mente che dobbiamo fare delle modifiche al codice per gli algoritmi che usano l’elemento di ricerca per i calcoli numerici, come l’algoritmo di ricerca per interpolazione.

Python è anche un buon punto di partenza se volete confrontare le prestazioni di diversi algoritmi di ricerca per il vostro set di dati; costruire un prototipo in Python è più facile e veloce perché potete fare di più con meno righe di codice.

Per confrontare le prestazioni dei nostri algoritmi di ricerca implementati con un dataset, possiamo usare la libreria del tempo in Python:

import timestart = time.time()# call the function hereend = time.time()print(start-end)

Conclusione

Ci sono molti modi possibili per cercare un elemento in una collezione. In questo articolo, abbiamo cercato di discutere alcuni algoritmi di ricerca e le loro implementazioni in Python.

Scegliere quale algoritmo usare si basa sui dati che dovete cercare; il vostro array di input, che abbiamo chiamato lys in tutte le nostre implementazioni.

• Se volete cercare in un array non ordinato o trovare la prima occorrenza di una variabile di ricerca, l’opzione migliore è la ricerca lineare.
• Se volete cercare in un array ordinato, ci sono molte opzioni di cui il metodo più semplice e veloce è la ricerca binaria.
• Se avete una matrice ordinata che volete cercare senza usare l’operatore di divisione, potete usare la ricerca a salti o la ricerca Fibonacci.
• Se sapete che l’elemento che state cercando è probabilmente più vicino all’inizio della matrice, potete usare la ricerca esponenziale.
• Se il vostro array ordinato è anche uniformemente distribuito, l’algoritmo di ricerca più veloce ed efficiente da usare sarebbe la ricerca per interpolazione.

Se non siete sicuri di quale algoritmo usare con un array ordinato, provate ognuno di essi con la libreria dei tempi di Python e scegliete quello che funziona meglio con il vostro set di dati.