Vector

Le liste sono la struttura dati “fondamentale” nei linguaggi funzionali, ma hanno dei limiti che vanno considerati quando bisogna scegliere se usarle nelle applicazioni. Il problema principale è che esse sono strutture lineari: per accedere all’elemento in posizione $n$ è necessario scorrere i primi $n$ elementi della lista. Perciò, il package scala.collection.immutable fornisce un’altra struttura dati immutabile, la classe generaica Vector[+T] (covariante nel tipo degli elementi), che implementa sequenze di elementi con operazioni di accesso più efficienti rispetto a quelle su List.

Un Vector[T] è rappresentato come un albero nel quale ciascun nodo può contenere al più 32 elementi di tipo T oppure i puntatori ad al più 32 nodi dell’albero (ma non può contenere un mix di elementi e puntatori). Tale struttura dati non ha un nome standard in letteratura, ma a volte è chiamata bitmapped vector trie, e ne esistono diverse varianti.

L’organizzazione dell’albero che rappresenta un Vector varia in funzione del numero $N$ di elementi che esso contiene, ad esempio:

• Se $N\leq 32$ l’albero consiste nella sola radice, la quale contiene direttamente gli elementi:

  

• Se $32 < N \leq 32^2$ l’albero ha due livelli:

  

  la radice contiene i puntatori ai massimo 32 nodi di secondo livello, ciascuno dei quali contiene 32 elementi (tranne il primo e l’ultimo nodo, che possono contenere meno elementi se l’albero non è pieno, $N < 32^2$).

• Se $32^2 < N\leq 32^3$ l’albero ha tre livelli:

  

  la radice contiene i puntatori ai massimo 32 nodi di secondo livello, ciascuno dei quali contiene a sua volta i puntatori a 32 nodi di terzo livello, che infine contengono gli elementi (anche in questo caso, il primo e l’ultimo nodo di ciascun livello possono contenere meno di 32 puntatori o elementi).

In generale, l’altezza dell’albero (il numero di livelli) è proporzionale a $\log_{32}N$, dunque pochi livelli sono sufficienti a contenere un’enorme quantità di dati: ad esempio, un Vector con 6 livelli può memorizzare $32^6 = 2^{30}$ elementi.

Accesso

L’accesso a un elmento di un Vector richiede un numero di livelli di indirettezza pari al numero di livelli dell’albero meno uno.

Ad esempio, l’accesso a un elemento di indice $n$ in un Vector rappresentato da un albero a 3 livelli richiede due livelli di indirettezza, perchè avviene nel seguente modo:

1. (primo livello di indirettezza) Dalla radice si raggiunge il nodo di secondo livello che è radice del sottoalbero contenente l’elemento cercato tramite il puntatore che è radice del sottoalbero contenente l’elemento cercato tramite il puntatore situato all’indice $n / 32^2$ della radice. Infatti, siccome ciascun sottoalbero della radice contiene $32^2$ elementi, l’elemento si trova all’interno del sottoalbero di indice $n/32^2$, e in tale albero ha l’indice $n\ \% \ 32^2$.
2. (secondo livello di indirettezza) Da questo nodo di secondo livello si raggiunge il nodo di terzo livello contenente l’elemento cercato tramite il puntatore di indice $(n \ \% \ 32^2) / 32$ (in base a un ragionamento analogo a quello del passo precedente, con la differenza che qui i sottoalberi contengono 32 elementi ciascuno).
3. Infine, in questo nodo di terzo livello si accede direttamente all’elemento di indice $(n \ \% \ 32^2) \ \% \ 32$, che è quello cercato.

Come esempio specifico, si supponga di voler accedere all’elemento in posizione $n = 32$:

1. l’indice del nodo di secondo livello è $n / 32^2 = 32/32^2 = 0$, che dalla radice si raggiunge tramite il puntatore $p_0$
2. l’indice del nodo di terzo livello è $(n\ \%\ 32^2) /32 = (32 \ \%\ 32^2)/32 = 32/32 = 1$, che dal nodo di secondo livello si raggiunge tramite il puntatore $p_1$
3. l’indice dell’elemento del nodo di terzo livello è $(n \ \% \ 32^2)\ \%\ 32 = (32 \ \%\ 32^2)\ \%\ 32 = 32 \ \% \ 32 = 0$, cioè l’elemento a cui si vuole accedere è $e_0$.

Siccome il numero di operazioni necessarie per l’accesso dipende dall’altezza dell’albero, esso è in generale proporzionale a $\log_{32}N$. Ciò significa che i Vector hanno buone prestazioni nel caso dell’accesso per indice agli elementi (al contrario delle liste). Inoltre, essi hanno buone prestazioni anche nel caso di operazioni come map e fold (ma tali operazioni sono efficienti anche sulle liste).