Scegliere una struttura dati

Tra 1023 chiavi, una ricerca lineare di una chiave assente fa 1023 confronti, la ricerca binaria ne fa 10, e una tabella hash con 1023 bucket ne ha fatti al massimo 6 nel laboratorio.

Parti dalle domande che farai

Nessuna struttura è la migliore in tutto. Ognuna rende economiche alcune operazioni rendendone costose altre, quindi per scegliere bisogna elencare che cosa farà più spesso il tuo programma. Il corso 6.006 del MIT divide le possibilità in due interfacce. Una sequenza tiene gli elementi in un ordine deciso da te (primo, secondo, terzo), e chiedi gli elementi per posizione. Un insieme (set) tiene gli elementi per chiave, e chiedi se una chiave c'è, oppure la chiave più piccola, oppure quella che segue una chiave data. Un insieme senza le domande sull'ordine si chiama dizionario.

Alcune situazioni comuni e la risposta di solito giusta:

• Leggere elementi per posizione, aggiungere in fondo: un array dinamico (un array JavaScript).
• Cronologia di Annulla, parentesi bilanciate, visita in profondità: una pila, cioè un array usato solo alla fine.
• Lavori gestiti in ordine di arrivo, visita in ampiezza: una coda, con un indice di testa o un buffer circolare invece di shift su un array lungo.
• Cercare cose per nome o id: una tabella hash, che in JavaScript vuol dire Map o Set.
• Tenere le chiavi ordinate mentre inserisci ed elimini, chiedere la chiave successiva: un albero binario di ricerca bilanciato.
• Molti inserimenti ed eliminazioni in un punto che hai già in mano: una lista concatenata.

La stessa ricerca in cinque strutture

Il laboratorio qui sotto memorizza le stesse chiavi in cinque modi e conta i confronti necessari per trovarne una. Le chiavi sono 15, 127 o 1023 numeri interi casuali. L'array non ordinato usa la ricerca lineare. L'array ordinato usa la ricerca binaria. L'albero bilanciato è stato costruito inserendo prima le chiavi centrali, quindi è il più basso possibile. L'altro albero è stato costruito dalle chiavi in ordine crescente, quindi è una catena. La tabella hash ha tanti bucket quante chiavi e conta 1 per il calcolo di h(k).

Con 15 chiavi le differenze sono piccole: la ricerca lineare richiede in media 8 confronti e la ricerca binaria circa 3.3. Con 1023 chiavi non lo sono. La ricerca lineare ne richiede in media 512 e 1023 per una chiave assente, mentre la ricerca binaria e l'albero bilanciato non ne richiedono mai più di 10. L'albero a catena è cattivo quanto la ricerca lineare. La tabella hash resta in media tra 2.3 e 2.5 a ogni dimensione perché le sue catene restano corte, e in questo laboratorio il suo caso peggiore per 1023 chiavi è stato 6. Ecco perché Map è la scelta predefinita per le ricerche, e perché le strutture ordinate valgono la pena solo quando ti serve anche l'ordine.

Ogni cella di queste due tabelle è la velocità di crescita del costo per n elementi, secondo le tabelle degli appunti delle lezioni 2, 4 e 7 del MIT. Tabelle hash e alberi di ricerca compaiono solo nella seconda tabella perché lavorano per chiave, non per posizione. In un array non ordinato o in una lista, inserire una chiave costa n perché prima devi controllare che non ci sia già. L'array ordinato trova in fretta ma deve spostare valori per fare spazio a una nuova chiave.

Map od oggetto?

I programmi JavaScript usano spesso un oggetto semplice come dizionario, scrivendo prices["apple"]. MDN elenca alcuni motivi per preferire Map quando le chiavi vengono dai dati: un oggetto ha un prototipo, quindi contiene chiavi predefinite che potrebbero scontrarsi con le tue; una Map può usare qualsiasi valore come chiave, non solo stringhe e simboli; la sua dimensione è una sola proprietà, map.size; e viene percorsa nell'ordine di inserimento. Gli oggetti restano la scelta naturale per record con un insieme fisso di campi con nome.