venerdì 18 luglio 2014

Algoritmi di sorting, questi sconosciuti



Bentornati sulle pagine di questo blog!
Cosa ci inventeremo stavolta per annoiarvi a morte? Sì, lo so, facciamo del nostro meglio ogni volta, e credo proprio che lo scopo sia quasi sempre raggiunto!
Oggi...oggi...oggi, di cosa volevo parlare? ...Ah si, algoritmi. Algoritmi di sorting.
Ok, parto dal presupposto che chi legga non sappia nulla, ma proprio nulla, nemmeno di algoritmi.

Bene, cos'è un algoritmo? Si definisce algoritmo un numero finito di istruzioni che, in un numero finito di passi, da un input finito iniziale A porta sempre e solo in uno stato finale B. Un classico esempio potrebbe essere l'algoritmo che calcola un numero della successione di Fibonacci. L'algoritmo riceve in ingresso n, e restituisce l'ennesimo numero della successione.
Passiamo ora al complemento di specificazione: “di sorting”. Sorting significa ordinamento, quindi parleremo degli algoritmi che cercano di ordinare una serie di oggetti (nel nostro caso numeri naturali) secondo una data relazione d'ordine (nel nostro caso ordine crescente).
Uno può benissimo chiedersi “ma che ca**o me ne faccio di sta roba?”, ma se vi fermaste un attimo a pensare, capireste subito che l'ordinamento (o la classificazione, più in generale) è alla base di praticamente tutte le attività umane.
Avete presente quell'ammasso informe di file di tipi diversi e con nomi assurdi che avete nella cartella Downloads del vostro pc? Immaginate se non esistesse quella splendida opzione "Ordina per...{tipo, nome, ultima_modifica, dimensione}"...vi sfiderei a trovare quel "xxx.avi" che tanto vorreste avere sottomano al momento!
Questo è solo un esempio marginale dell'importanza di tali algoritmi.

La domanda che porrei al lettore è la seguente: “hai 10 numeri naturali. Riesci a immagire un algoritmo per ordinarli dal minore al maggiore?”. Starete pensando “e se io non riesco a immaginare un algoritmo, ma solo donne nude?”; ammetto che sarebbe senz'altro una tesi ferrea la vostra.
Siccome sono convinto che prendereste questa sfida nella maggior parte dei casi sottogamba, essendo portati a pensare “e ci vuole un algoritmo per far sta roba?”, senza riflettere che se invece di 10 numeri fossero 100 milioni sarebbe un attimo più complicato, vi indico direttamente qualcuno tra gli algoritmi più famosi.

Non ho idea se qualcuno perderà davvero del tempo a pensarci, ma credo che la soluzione più banale, benché non sia il primo algoritmo che si studi solitamente, è quello che viene chiamato Selection Sort.
Praticamente, esso ci dice di cercare all'interno della nostra sequenza il minimo, e metterlo come primo elemento. Dunque procedere scansionando gli n – 1 numeri rimanenti cercando il nuovo minimo, e avanti così. Dopo n – 1 scambi (l'ultima iterazione avrà un solo intero che sarà già il maggiore, evidentemente), la nostra sequenza sarà ordinata. Ha l'enorme vantaggio, rispetto ad altri algoritmi, di essere facilmente implementabile (ossia è molto facile da programmare), e di non avere caso migliore o peggiore, cioè il tempo impiegato dall'algoritmo dipende esclusivamente dalla lunghezza della sequenza che vogliamo ordinare, non dalla posizione di ciascun numero nella sequenza. Il numero di scambi è perciò fisso, ed è, come detto in precedenza, n – 1.
Questo algoritmo prevede quindi due cicli, uno esterno da i = 0 a n – 1; l'altro, interno, da i + 1 a n. Per un totale di n * (n – 1) / 2 confronti, ossia asintotico a n^2 (chiunque abbia studiato un minimo di calcolo infinitesimale sa che basta far tendere nell'espressione precedente n a infinito).

Il secondo algoritmo, anch'esso molto famoso, è il Bubble Sort (nome simpatico, eh?). Quest'ultimo prevede l'ordinamento “a bolla” della sequenza: viene definito prendendo a due a due gli elementi adiacenti della nostra sequenza e spostando a sinistra il minore, ad esempio:
3 1 2 → 1 3 2 → 1 3 2 → 1 2 3.
Sì, l'effetto “a bolla” lo vedrete solo dopo esservi fumati un cannone; cito wikipedia:
L'algoritmo deve il suo nome al modo in cui gli elementi vengono ordinati, con quelli più piccoli che "risalgono" verso le loro posizioni corrette all'interno della lista così come fanno le bollicine in un bicchiere di spumante.
Evidente no?
Questo algoritmo è noto per essere il primo che si studia, nonché mediamente il più inefficiente battuto solo dallo stupid sort, che consiste nel continuare a mischiare a casaccio gli elementi finché non ne esce fuori una sequenza ordinata (una bella presa per il culo eh!). D'altra parte è risaputo che localmente l'entropia possa diminuire, perciò perché non tentare?
Il Bubble Sort differisce tra caso migliore e peggiore. Il caso medio asintoticamente è molto simile al peggiore. Prendiamo come caso migliore una sequenza già ordinata: il Bubble Sort non farà alcuno scambio, ma dovrà comunque fare circa n^2 confronti (come il precedente Selection Sort).
Vale lo stesso numero di confronti anche per gli altri casi, ma il numero di scambi nel caso medio e peggiore sarà sempre nell'ordine del n^2 (contro gli n – 1 del precedente algoritmo). Come caso peggiore si prende una sequenza ordinata in maniera opposta a come la vogliamo noi (ad esempio, vogliamo ordinare in maniera crescente una sequenza già ordinata in maniera decrescente). Appare evidente che il primo ciclo porterà, attraverso n - 1 scambi, il primo elemento (il maggiore) in coda alla sequenza, poi toccherà al secondo, ecc ecc.

Ora direi che è il momento di vedere un algoritmo più complesso, per avere una vaga idea di quanto si sia arrivati ad astrarre e a congetturare.
Il Quick Sort si basa sul paradigma divide et impera, e prevede di spezzare la nostra sequenza in due parti, prendendo un perno a caso al suo interno; gli interi minori del perno staranno a sinistra e quelli maggiori a destra. Poi si va avanti a fare lo stesso su ciascuna delle due sequenze così create, finché non si arriva ad avere minisequenze ordinate. Quindi si unisce il tutto. Voi penserete “oltre a essere così incasinato, ha almeno dei vantaggi?”, e la risposta è affermativa. Questo algoritmo sfrutta perfettamente le capacità dei processori moderni di gestire il multithreading, e soprattutto si rivela l'algoritmo più efficiente tra quelli basati sul confronto degli elementi nella sequenza. Tranne nel caso peggiore, in cui ha le stesse prestazioni dei precedenti algoritmi, esso permette un numero di confronti notevolmente minore rispetto ad essi.
Prendiamo ad esempio la sequenza
4 7 1 5 3, dove il perno è sottolineato. Contiamo il numero di confronti e di scambi; in questo caso sarebbero 10/4 per Selection Sort e 12/6 per Bubble Sort). Con Quick Sort si ha:
3 1 4 7 5 → 4 confronti + 2 scambi. Ora spezziamo nelle due sotto sequenze e prendiamo dei nuovi pivot.
3 1; 7 5 , che diventano 1 3; 5 7 con altri 2 confronti e 2 scambi.
Ora siamo già pronti a riordinare il tutto, dopo solo 6 confronti e 4 scambi!
Ovviamente è solo un esempio preso appositamente per far notare le differenze (anche se rientra nella casistica media), ma si può intuire come su enormi quantità di dati, quest'ultimo algoritmo risulti notevolmente migliore.
Inoltre è possibile migliorarne ancora l'efficienza scegliendo dei perni più adatti, calcolati attraverso procedimenti euristici.


"Oh! Suona la campanella...confido ragionevolmente, visto l'interesse della classe, che mi lascerete 2 minuti dell'intervallo per terminare il disc...ma no, fermi alunni, dove state andando! Sto concludendo la spiegaz..." 
"Si fotta, prof!"
"Lezione conclusa...sigh..."
Siete ancora convinti sia così inutile e banale ordinare una serie di oggetti?
Un ulteriore esempio di utilizzo di questi algoritmi, coniato dalla folle mente del Maestro Jedi +Gianfranco Gallizia, riguarda un elenco ordinato alfabeticamente; si vuole sapere in che posizione si trova la parola Xerxes. Idea stupida: si legge l'elenco da Abecedario a Zuzzurellone e ci si ferma quando si arriva a Xerxes. Idea meno stupida: si va direttamente a metà dell'elenco e si legge cosa c'è, se è Xerxes abbiamo finito altrimenti si confronta la parola e si decide se cercare nella prima metà o nella seconda ripetendo il procedimento.
Caso peggiore nella ricerca lineare (la prima idea): ci tocca leggere tutto l'elenco.
Caso peggiore nella ricerca binaria: ci tocca leggere un numero di elementi pari al logaritmo in base 2 della lunghezza dell'elenco.
Cosa cambia? Negli elenchi brevi (3 o 5 elementi) nulla (o quasi), negli elenchi di un milione di elementi, si passa da un milione di letture a 20 letture. Se il tuo elenco è ordinato la ricerca binaria è un must. Se il tuo elenco non è ordinato e fai moltissime letture ti conviene ordinarlo prima.
Se si vuole poi un esempio ancora più concreto: ogni volta che ci si logga su un sito il server deve vedere se il nome utente che viene inserito è corretto e se la password associata corrisponde. Facebook ha più di un miliardo di utenti (attivi e non attivi) e deve fare questa ricerca ogni volta che un utente tenta il login.

Beh direi che con questi ultimi esempi si è chiarito perfettamente l'importanza di questi algoritmi che va molto oltre il campo dell'informatica, e che arrivano, in maniera del tutto trasparente all'utente (come d'altra parte lo è tutta l'informatica, e forse rappresenta il motivo per cui la trovo così splendida), a migliorare notevolmente tantissimi servizi che si utilizzano quotidianamente.
Che altro dire? Al prossimo noiosissimo articolo!
E intanto, buone ferie a tutti!