Seguici su Telegram, ne vale la pena ❤️ ➡ @trovalost
Vai al contenuto

Algoritmi di ricerca ed ordinamento: una panoramica generale in Python

Tag:

Fin dagli albori dell’informatica ci si è posti il problema di risolvere in modo efficiente due problemi ricorrenti: da un lato l’ordinamento dei dati, dall’altro la ricerca efficente degli stessi. Questo presenta degli indubbi vantaggi in termini di evoluzione tecnologica: se posso ordinare rapidamente dei dati, o mantenerli ordinati o darmi comunque una regola per metterli in fila, non sarò costretto a cercarli “alla cieca”.

Risparmierò tempo, risorse e soldi, senza contare che potrò serializzare le istruzioni, farle eseguire rapidamente anche su grandi quantità di dati e via dicendo. Inoltre la ricerca potrà avvenire in modo efficiente non solo sfruttando più indici o più tecniche matematiche a supporto, ma anche facendo leva proprio sull’ordinamento. Poichè in informatica tutto è numero (nel senso che tutto si può rappresentare e/o gestire come stringa di bit, o al limite come i corrispondenti numeri interi) è chiaro che il problema è stato sviscerato in lungo e in largo.

Modello di base

Tanto per fissare le idee, assumiamo come modello base di avere i nostri dati all’interno di un array Python (una struttura dati che contiene numeri interi, essenzialmente, ma nulla esclude che i numeri possano essere ad esempio stringhe, per estensione). Per chi non ricordasse la sintassi, un array Python si può rappresentare come segue:

arr = [7, 2, 9, 4, 5]

il che significa che avremo 5 elementi interi di cui:

  • il primo è 7 (indice 0, ovvero arr[0]);
  • il secondo è 2 (indice 1, quindi arr[1]);
  • e così via.

Algoritmi di ricerca

Linear Search – Ricerca lineare in Python

Il modo più newbie o “ingenuo” per fare una ricerca è quello di scorrere gli elementi uno per uno; già Alan Turing aveva avuto questa intuizione nel 1936 ideando la macchina di Turing, l’astrazione teorica per rappresentare una macchina in grado di effettuare calcoli di ogni genere leggendo i dati (una sequenza di bit, dai valori 0 e 1 uniti ad un eventuale blank o spazio). Se devo cercare un elemento tra 5 valori, chiaramente vado a fare la ricercapartendo dall’elemento zero (arr[0]) e mi fermo quando sarò arrivato alla fine (senza trovare l’elemento che volevo) oppure se dovessi incocciarlo per strada durante la ricerca (ad esempio arr[2] oppure arr[5]).

Come regola generale, la dimensione di arr sarà len(arr), il primo elemento di arr sarà arr[0] mentre l’ultimo sarà arr[len(arr)-1].

La ricerca lineare in Python si implementa come segue:

  • Si parte dall’elemento più a sinistra di arr[] e si confronta uno per uno x con ogni elemento di arr[].
  • Se x corrisponde a quello che sto cercando, si restituisce l’indice (“ho trovato il valore”).
  • Se x non corrisponde a nessuno degli elementi presenti in arr, l’algoritmo restituisce -1 (“mi dispiace, non lo trovo”).

In Python significa scrivere, ad esempio:

def linear_search(arr, x):
    for i in range(len(arr)): #per tutti gli elementi da 0 a len(arr)-1
        if arr[i] == x:
            return i
    return -1

arr = [5, 7, 3, 9, 5, 2]

linear_search(arr, 3) # restituisce 2

linear_search(arr, 66) # restituisce -1

Binary Search – Ricerca binaria in Python

L’approccio lineare funziona nella misura in cui i dati sono pochi e costa poco confrontarli: se i dati diventano della cardinalità di milioni o oltre, diventa complicato scorrere un nastro con milioni di confronti. Motivo per cui gli informatici si sono inventati la ricerca binaria, che non ha a che vedere con i treni e tantomeno con i numeri 0 e 1: ha a che fare, semmai, con la possibilità di dimezzare lo spazio di ricerca, a condizione che i dati siano stati preventivamente ordinati dal più piccolo al più grande (o vicersa). La ricerca binaria è un algoritmo elegante, relativamente semplice e soprattutto molto efficiente: se ad esempio abbiamo 1024 elementi tra cui cercare un elemento x, con la ricerca binaria nel caso peggiore basteranno circa log2(1024) = 10 confronti, 2 ordini di grandezza in meno del fare 1024 confronti lineari (ammesso, in tal caso, che l’algoritmo vada a cercare un elemento in ultima posizione). Se abbiamo N elementi, la ricerca lineare dimezza progressivamente lo spazio di ricerca ed impiega pessimisticamente log2(N) confronti in tutto.

La ricerca binaria, pertanto, fissa due indici limite low (indice basso) e high (indice alto) e prova a cercare x coerentemente con la struttura ordinata su cui sta lavorando. Ogni volta, nello specifico, continuerà a cercare a destra oppure a sinistra a seconda dei casi.

In Python possiamo costruire una elegante funzione ricorsiva, ovvero che richiama se stessa più volte costruendo uno stack o pila di memoria, fino a dare una risposta all’utente:

def binary_search(arr, low, high, x):
    # finchè ci sono elementi da cercare...
    if high >= low:
        mid = (high + low) // 2 # divisione intera per 2
        # trovato?
        if arr[mid] == x:
            return mid
        # cerca a sinistra
        elif arr[mid] > x:
            return binary_search(arr, low, mid - 1, x)
        # cerca a destra
        else:
            return binary_search(arr, mid + 1, high, x)
    else:
        # mi dispiace, l'elemento non c'è
        return -1
# test
arr = [ 1, 10, 16, 67, 156, 159, 2020, 2024 ]
trovato =binary_search(arr, 0, len(arr)-1, 2020) # restituisce 6
trovato =binary_search(arr, 0, len(arr)-1, 3636) # restituisce -1

Per provare a capire ancora meglio, potete guardare questo video di una danza che modellizza esattamente il processo, e chiarisce anche un aspetto non da poco: il numero che stiamo cercando è visibile all’algoritmo solo durante l’accesso, non globalmente, anche se noi da umani lo leggiamo direttamente e sapremmo indicarlo anche “ad occhio”.

Algoritmi di ordinamento

Le tecniche di ordinamento sono varie, e anche qui la letteratura è molto ricca. Ci limitiamo ad elencare due tra i più celebri algoritmi di ordinamento in informatica: il primo è l’ordinamento a bolle o bubble-sort, il secondo è il quick sort (molto usato nella pratica per ordinare grandi quantità di dati).

Bubble sort – Ordinamento a bolle in Python

Il Bubble sort è un algoritmo che mette a confronto ogni coppia di elementi organizzati in una struttura apposita, e li scambia se non sono in ordine – il tutto fino a quando l’intera struttura non è ordinata. Per ogni elemento dell’elenco, l’algoritmo confronta ogni coppia di elementi. Su Youtube esiste la serie di video Algo-Rythmics che modellizza in modo originale vari algoritmi – e li fa capire, soprattutto – sfruttando ballerini con dei numeri interi riportati sul dorso.

def bubbleSort(arr):
    n = len(arr)
    # optimize code, so if the array is already sorted, it doesn't need
    # to go through the entire process
    swapped = False
    # Traverse through all array elements
    for i in range(n-1):
        # range(n) also work but outer loop will
        # repeat one time more than needed.
        # Last i elements are already in place
        for j in range(0, n-i-1):
            # traverse the array from 0 to n-i-1
            # Swap if the element found is greater
            # than the next element
            if arr[j] > arr[j + 1]:
                swapped = True
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
        if not swapped:
            # if we haven't needed to make a single swap, we
            # can just exit the main loop.
            return
# Driver code to test above
arr = [64, 34, 25, 12, 22, 11, 90]
bubbleSort(arr)

Quick sort in Python

QuickSort è un algoritmo molto efficente che segue la politica divide et impera, ovvero scomponi un problema grosso in mini sottoproblemi più piccoli, risolvili uno per uno e ricomponi la risposta di conseguenza. Quick sort seleziona un elemento a titolo di perno del suo ordinamento, poi divide l’array dato attorno allo stesso. Tale elemento può essere scelto secondo varie strategie, trab cui ad esempio, scegli il primo, l’ultimo, l’elemento intermedio oppure, banalmente, uno a caso.

In questa implementazione si scegliere l’ultimo elemento come perno del quick sort.

quickSort(arr[], low, high) {

  // finchè ci sono elementi da ordinare...
  if (low < high) {

    // pi indice di partizione su arr, tra low e high correnti
    pi = partition(arr, low, high);

    // ordina prima l'indice pi
    quickSort(arr, low, pi - 1);
    // ordina dopo l'indice pi
    quickSort(arr, pi + 1, high);
  }
}

la partizione nello specifico viene implementata come segue:

def partition(array, low, high):
    pivot = array[high]
    i = low - 1
    for j in range(low, high):
        if array[j] <= pivot:
            i = i + 1
            (array[i], array[j]) = (array[j], array[i])
    (array[i + 1], array[high]) = (array[high], array[i + 1])
    return i + 1

Di seguito il consueto ballo ungherese che mostra l’algoritmo di ordinamento quick sort in modo coreografico.

 

👇 Da non perdere 👇

Questo portale esiste da 4463 giorni (12 anni), e contiene ad oggi 6820 articoli (circa 5.456.000 parole in tutto) e 13 servizi online gratuiti. – Leggi un altro articolo a caso
Non ha ancora votato nessuno.

Ti sembra utile o interessante? Vota e fammelo sapere.

Leggi anche:
Questo sito contribuisce alla audience di sè stesso.
Il nostro network informativo: Lipercubo.it - Pagare.online - Trovalost.it.