Le strutture dati spiegate
Ogni programma conserva i dati da qualche parte, e il modo in cui lo fa decide che cosa è veloce e che cosa è lento. Un elenco di un milione di nomi si può scorrere nome per nome, oppure ordinare in modo che venti confronti trovino qualsiasi nome. Le strutture dati sono queste organizzazioni: una manciata di idee, quasi tutte più vecchie del personal computer, che stanno dentro ogni database, sistema operativo, browser e videogioco.
A che cosa serve una struttura dati
Una struttura dati si sceglie in base alle domande a cui deve rispondere. Il registro chiamate di un telefono vuole prima l'ultima chiamata, la coda di una stampante prima il lavoro più vecchio, un dizionario il significato di una parola fra centomila, un navigatore l'incrocio non visitato più vicino. Ogni struttura rende veloci alcune operazioni rinunciando ad altre, e la notazione O grande descrive lo scambio: O(1) significa che il tempo non cresce con il numero n di elementi, O(log n) che raddoppiare n aggiunge un passo, e O(n) che il tempo cresce in proporzione a n.
Pile, code e deque
Una pila aggiunge e toglie allo stesso capo: ultimo a entrare, primo a uscire. Le cronologie di annullamento, il pulsante Indietro e le chiamate di un programma in esecuzione sono pile. Una coda aggiunge in fondo e toglie dal fronte: primo a entrare, primo a uscire, come l'input da tastiera o una coda di stampa. Una deque permette entrambe le cose a entrambi i capi. Tutte e tre richiedono tempo costante per operazione. Una coda è spesso tenuta in un buffer circolare, un array fisso in cui fronte e fondo girano oltre la fine; quando si riempie, gli elementi vengono copiati in un array grande il doppio. La copia costa O(n), ma succede così di rado che ogni operazione costa comunque O(1) in media, il cosiddetto limite ammortizzato.
Liste concatenate
Una lista concatenata memorizza ogni valore in un nodo con un puntatore al nodo successivo. Inserire o cancellare cambia solo uno o due puntatori, senza spostare nulla, ma non si può saltare al decimo nodo: si seguono i collegamenti dalla testa. Una lista che tiene solo la testa raggiunge la coda in O(n) passi; le liste reali tengono di solito anche un puntatore alla coda, e quelle doppiamente concatenate un puntatore all'indietro, ed è così che si costruiscono la cronologia di un browser o una cache LRU.
Alberi binari di ricerca
Un albero binario di ricerca tiene, in ogni nodo, i valori più piccoli nel sottoalbero sinistro e quelli più grandi nel destro. Una ricerca confronta e va a sinistra o a destra, e una visita in ordine legge i valori ordinati. Cancellare una foglia significa toglierla, un nodo con un figlio viene sostituito da quel figlio, e un nodo con due figli dal suo successore in ordine, il valore più piccolo del suo sottoalbero destro. Tutto ciò richiede un tempo proporzionale all'altezza dell'albero: circa log n quando l'albero è folto, ma n quando i valori arrivano già ordinati e l'albero degenera in una lista.
Alberi AVL e rosso-neri
Gli alberi autobilancianti riparano la loro forma dopo ogni modifica. Un albero AVL, inventato da Adelson-Velsky e Landis nel 1962, tiene le altezze dei due sottoalberi di ogni nodo entro uno l'una dall'altra; quando il fattore di bilanciamento di un nodo arriva a ±2, una rotazione (i casi LL e RR) o due (LR e RL) ripristinano l'equilibrio. Un albero rosso-nero colora i nodi in modo che la radice sia nera, nessun nodo rosso abbia un figlio rosso e ogni percorso verso il basso attraversi lo stesso numero di nodi neri, il che tiene il percorso più lungo al massimo doppio del più corto. Si ripara ricolorando e con al più poche rotazioni, ed è l'albero dentro la TreeMap di Java, std::map del C++ e lo scheduler di Linux.
Heap e code di priorità
Un heap binario è un albero binario completo salvato in un array senza alcun puntatore: i figli della posizione i stanno a 2i + 1 e 2i + 2. In un min-heap ogni genitore è al massimo grande quanto i suoi figli, quindi il valore più piccolo è sempre nella radice. Un nuovo valore va in fondo e risale oltre i genitori più grandi; estrarre la radice porta l'ultimo valore in cima e lo fa scendere. Entrambe le operazioni costano O(log n), e un intero array si trasforma in heap in O(n). Gli heap fanno girare le code di priorità dei cammini minimi di Dijkstra, delle simulazioni a eventi e degli scheduler dei sistemi operativi, e danno l'heapsort.
Tabelle hash
Una tabella hash trasforma una chiave in un indice dell'array con una funzione hash e ci va direttamente. Chiavi diverse possono finire sullo stesso indice: è una collisione. Il concatenamento tiene una piccola lista in ogni bucket; l'indirizzamento aperto, come la scansione lineare, prova le celle successive finché non ne trova una libera e, quando una chiave viene cancellata, deve lasciare una lapide perché le ricerche successive continuino a scandire. Con una buona funzione hash e un fattore di carico (chiavi per bucket) tenuto basso facendo crescere la tabella, inserimento, ricerca e cancellazione costano O(1) in media. Una funzione scadente, come sommare i codici dei caratteri di una parola, manda gli anagrammi nello stesso bucket. Le tabelle hash stanno dietro ai dict di Python, agli oggetti di JavaScript e agli indici dei database.
Trie e union-find
Un trie, o albero dei prefissi, memorizza le stringhe un carattere per livello, così le parole con lo stesso inizio condividono un percorso e un nodo segna dove finisce una parola. Trovare una parola di lunghezza L richiede L passi, per quante parole ci siano, e tutte le parole con un certo prefisso stanno in un unico sottoalbero: così funzionano il completamento automatico e i correttori ortografici. Union-find tiene gli elementi in insiemi disgiunti, ognuno un albero la cui radice dà il nome all'insieme. Find segue i collegamenti al genitore fino alla radice; union appende una radice sotto un'altra. Con l'unione per rango e la compressione dei cammini, una lunga serie di operazioni costa un tempo quasi costante ciascuna, la funzione di Ackermann inversa α(n), che vale al massimo 4 per ogni n realistico. L'algoritmo di Kruskal per l'albero ricoprente minimo si basa su di essa.
Domande frequenti
Che differenza c'è tra un array e una lista concatenata?
Un array tiene gli elementi uno accanto all'altro in memoria, quindi ogni posizione si raggiunge subito, ma inserire nel mezzo significa spostare tutto ciò che segue. Una lista concatenata può inserire ovunque cambiando puntatori, ma raggiungere una posizione significa camminare dalla testa. Gli array sfruttano anche molto meglio la cache del processore, ed è per questo che in pratica sono di solito più veloci.
Che cosa significa tempo ammortizzato?
Il costo medio per operazione su una lunga serie, anche se una singola operazione a volte è costosa. Un buffer circolare che raddoppia quando è pieno copia ogni tanto tutti gli n elementi, ma poiché le copie diventano più rare man mano che il buffer cresce, n inserimenti costano O(n) in totale, cioè O(1) ciascuno in media.
Un heap è la stessa cosa di un albero binario di ricerca?
No. Un albero binario di ricerca mette ogni sottoalbero sinistro prima del suo nodo e ogni sottoalbero destro dopo, quindi può elencare tutti i valori in ordine e trovare in fretta qualsiasi valore. Un heap promette solo che ogni genitore viene prima dei suoi figli, il che basta per trovare subito il minimo o il massimo ma non per cercare un valore qualsiasi.
Come fa union-find a sapere se due elementi sono collegati?
Segue i collegamenti al genitore da ciascun elemento fino alla radice del suo albero. Se entrambi arrivano alla stessa radice, sono nello stesso insieme. La compressione dei cammini fa poi puntare ogni nodo del percorso direttamente alla radice, così la domanda successiva su di loro richiede un solo passo.
Pronto a provarlo?
Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.
Apri il visualizzatore di strutture dati