Code

Togliere il primo di 1000 valori da un array di JavaScript con shift sposta gli altri 999; un buffer circolare fa lo stesso lavoro in un passo.

Il primo entrato è il primo a uscire

Una coda è la fila al bancone di un negozio. Le persone si mettono in fondo e vengono servite dalla testa, così chi è arrivato per primo esce per primo. La regola è first in, first out (FIFO): il primo entrato è il primo a uscire. Le due operazioni sono accodare (enqueue), che aggiunge un valore in fondo, ed estrarre (dequeue), che toglie il valore in testa. Negli appunti del corso 6.006 del MIT una coda è l'interfaccia di sequenza limitata a insert last(x) e delete first().

Le code sono ovunque il lavoro vada gestito in ordine di arrivo: documenti in attesa di una stampante, tasti premuti in attesa di un programma, messaggi in attesa di un server. La visita in ampiezza, dal corso di algoritmi, tiene in una coda le caselle che deve ancora visitare, ed è proprio per questo che esplora ad anelli di uguale distanza.

Il modo facile e il suo costo nascosto

In JavaScript la coda più ovvia è un array: push per accodare in fondo e shift per estrarre dalla testa. Funziona, e per code corte va bene. Ma guarda che cosa fa shift. MDN dice che «sposta tutti i valori a sinistra di 1», e la specifica ECMAScript lo scrive come un ciclo che copia l'elemento k nella posizione k − 1 per ogni k. La testa di un array è l'estremità costosa, come ha mostrato la prima unità. Estrarre da una coda di n valori costa 1 lettura più n − 1 spostamenti, quindi una coda di 1000 valori costa 1000 passi a ogni estrazione. (I motori possono usare scorciatoie al loro interno, ma la specifica non promette niente.)

Se accodi 5 valori in un array vuoto e poi li estrai tutti e 5, gli accodamenti costano 5 passi e le estrazioni 5 + 4 + 3 + 2 + 1 = 15, per 20 in tutto. Gran parte di questo lavoro è spostare valori che non vengono nemmeno tolti.

Non spostare i valori, sposta la testa

La soluzione è smettere di spostare i valori e ricordare invece dov'è la testa. Tieni un indice chiamato head. L'estrazione legge il valore in head e aggiunge 1 a head; nient'altro si sposta. Il problema è che le celle prima di head vanno sprecate. Un buffer circolare (ring buffer) le riusa: l'array ha un numero fisso di celle, per esempio 8, e le posizioni ricominciano dall'inizio, così la cella dopo la 7 è la 0. Memorizza head e size. Il prossimo accodamento va nella cella (head + size) mod 8, e un'estrazione prende la cella head e porta head a (head + 1) mod 8. Entrambe le operazioni costano 1 passo. Il prezzo è una capacità fissa: quando size arriva a 8 la coda è piena, a meno di copiare tutto in un anello più grande come farebbe un array dinamico.

Quale conviene usare? Per una coda che non contiene mai più di qualche decina di valori, push e shift sono brevi e chiari, e gli spostamenti non costano quasi nulla. Per una coda attraverso cui passano migliaia di elementi, come le caselle di una grande visita in ampiezza, un indice di testa o un buffer circolare mantiene ogni estrazione a un passo, e la differenza cresce con la lunghezza della fila.