Array

Leggere il milionesimo valore di un array richiede un passo, ma mettere un nuovo valore in testa allo stesso array sposta un milione di valori.

Che cos'è una struttura dati

Un programma che tiene una lista di nomi, una coda di stampe o una tabella di prezzi deve memorizzare quei dati da qualche parte, e deve rispondere a domande su di essi: qual è il terzo elemento, questo nome è nella lista, quale stampa viene dopo? Una struttura dati è un modo di memorizzare i dati insieme ai metodi che rispondono a quelle domande. Il corso 6.006 del MIT separa qui due idee. L'interfaccia dice quali operazioni puoi chiedere, come «prendi l'elemento in posizione i» o «aggiungi un elemento alla fine». La struttura dati è il modo in cui quelle operazioni vengono davvero eseguite in memoria. Dietro una sola interfaccia possono esserci diverse strutture dati, e la loro velocità può essere molto diversa.

Questo corso conta i passi, come il corso di algoritmi, così due strutture si possono confrontare senza cronometro. In questa unità un passo è la lettura o la scrittura di una cella di memoria. Il laboratorio qui sotto li conta per te.

Un blocco di celle, una accanto all'altra

Un array memorizza i suoi valori in un unico blocco di memoria senza interruzioni, ogni valore in una cella della stessa dimensione, numerata da 0. È questa disposizione che rende gli array veloci da leggere. Se il blocco inizia all'indirizzo s e ogni cella occupa c byte, allora a[i] si trova all'indirizzo s + i × c. Il computer lo calcola con una moltiplicazione e un'addizione e salta direttamente lì, che i valga 3 o 3000000. Gli appunti del MIT indicano «get at(i)» e «set at(i, x)» per un array come Θ(1): il costo non cresce con la lunghezza.

La stessa disposizione rende lente le modifiche nel mezzo. Supponi che l'array contenga 7, 3, 9, 4, 6 e che tu voglia 1 in testa. Davanti al 7 non c'è spazio, quindi prima ogni valore deve spostarsi di una cella a destra, partendo dall'ultimo perché niente venga sovrascritto. Sono 5 spostamenti e 1 scrittura: 6 passi. Togliere il valore in testa è il contrario: lo leggi, poi sposti gli altri 4 valori di una cella a sinistra. Inserire in posizione i in un array di n valori costa n − i spostamenti più una scrittura, quindi la testa è il posto peggiore e la fine il migliore.

Quando il blocco è pieno

Un blocco di memoria ha una dimensione fissa: che cosa succede quando aggiungi un valore e tutte le celle sono occupate? L'array deve chiedere un blocco nuovo e più grande e copiarci ogni valore prima di poter scrivere quello nuovo. Nel laboratorio, un push sul blocco pieno di 5 costa 5 copie e 1 scrittura. Se l'array crescesse di una sola cella ogni volta, ogni push copierebbe tutto, e n push costerebbero circa n²/2 copie.

La soluzione descritta negli appunti del MIT è crescere molto in una volta, per esempio raddoppiando. Partendo da capacità 1, le copie avvengono quando l'array contiene 1, 2, 4, 8 e 16 valori, quindi 17 push costano in tutto 1 + 2 + 4 + 8 + 16 = 31 copie, meno di 2 per push. Un singolo push può ancora essere lento, ma una lunga serie di push ha in media un costo costante per push. Si parla di tempo Θ(1) ammortizzato. Visto da fuori, un array di JavaScript si comporta così: MDN descrive gli array come ridimensionabili, e push e pop lavorano alla fine, che è l'estremità economica.

const a = [7, 3, 9, 4, 6];
console.log(a[3]);      // 4, un passo
a.push(8);              // economico: la fine
a.unshift(1);           // ogni valore si sposta di una cella a destra
console.log(a.join(" ")); // 1 7 3 9 4 6 8