Array dinamico

In informatica, un vettore dinamico, vettore allargabile, vettore ridimensionabile, tabella dinamica, o lista di array è una struttura dati array che può essere ridimensionata e consente di aggiungere o rimuovere elementi. É fornita con la libreria standard in molti moderni linguaggi di programmazione principali.

Un array dinamico non è la stessa cosa di un array [[allocazione dinamica della memoria|allocato dinamicamente]], il quale è un array di dimensione fissa la quale è fissata quando l'array è allocato; per maggiori informazioni su questo tipo di array, vedere array.

Array dinamici di dimensione delimitata e capacità

L'array più semplice è costruito allocando un array di dimensione fissa e dividendolo in due parti: la prima memorizza gli elementi dell'array dinamico e la seconda è riservata, o inutilizzata. A questo punto è possibile aggiungere o rimuovere elementi dalla fine dell'array dinamico in tempo costante utilizzando lo spazio riservato, finchè questo spazio non viene completamente consumato. Il numero di elementi utilizzati per i contenuti dell'array dinamico è la sua dimensione logica o dimensione, mentre la dimensione dell'array sottostante è chiamata la capacita dell'array dinamico, la quale è la massima dimensione logica possibile.

Nelle applicazioni dove la dimensione logica è delimitata (bounded), questa struttura dati è sufficiente. Il ridimensionamento dell'array sottostante è un'operazione dispendiosa, che tipicamente coinvolge la copia dell'intero contenuto dell'array.

Espansione geometrica e costo ammortizzato

Per evitare di incorrere nel costo di ridimensionare molte volte, gli array dinamici si ridimensionano di grandi quantità, come raddoppiare le dimensioni, ed utilizzare lo spazio riservato per espansioni future. L'operazione di aggiunta di un elemento alla fine potrebbe funzionare come segue:

funzione inserisciFine(arraydin a, elemento e)
    se (a.dimensione = a.capacità)
        // ridimensiona a al doppio della sua capacità corrente:
        a.capacità ← a.capacità * 2  
        // (copia i coontenuti delle nuove locazioni quì)
    a[a.dimensione] ← e
    a.dimensione ← a.dimensione + 1

Man mano che gli n elementi vengono inseriti, le capacità formano una progressione geometrica. Espandere l'array di una qualsiasi proporzione costante assicura che l'inserimento di n elementi prende un tempo complessivo di O(n), ciò significa che ogni inserimento prende un tempo costante ammortizzato. Il valore di questa proporzione a porta a un compromesso spazio-tempo: il tempo medio per l'operazione di inserimento è circa a/(a-1), mentre il numero di celle perse è delimitata superiormente da (a-1)n. La scelta di a è indipendente dall'applicazione, ma un uso comune è a=2.

Molti array dinamici deallocano anche parte della memoria sottostante se la loro dimensione scende sotto una certa soglia, come il 30% della capacità.

Gli array dinamici sono un esempio comune quando si insegna analisi ammortizzata.

Prestazioni

	Lista concatenata	Array	Array dinamico
Indicizzazione	Θ(n)	Θ(1)	Θ(1)
Inserimento/rimozione alla fine	Θ(1)	N/A	Θ(1)
Inserimento/rimozione nel mezzo	Θ(1)	N/A	Θ(n)
Spazio perso (media)	Θ(n)	0	Θ(n)

L'array dinamico ha prestazioni simili all'array, con l'aggiunta delle nuove operazioni di aggiungere e rimuovere gli elementi dalla fine:

• Ottenere o impostare il valore a un particolare indice (tempo costante)
• Iterare attraverso gli elementi in ordine (tempo lineare, buone prestazioni di cache)
• Inserire o rimuovere un elemento dal mezzo dell'array (tempo lineare)
• Inserire o rimuovere un elemento alla fine dell'array (tempo costante ammortizzato)

Gli array dinamici beneficiano di molti vantaggi degli array, inclusa una buona località di riferimento e l'utilizzo di cache dati, compattezza (basso utilizzo di memoria), e accesso casuale. In genere hanno solo un piccolo carico per memorizzare le informazioni su dimensione e capacità. Questo rende gli array dinamici uno strumento attraente per la costruzione di strutture dati cache-fliendly.

Paragonati alle liste concatenate, gli array dinamici hanno un'indicizzazione più rapida (tempo costante contro tempo lineare) e tipicamente anche una più rapida iterazione grazie alla migliore località di riferimento; tuttavia, gli array dinamici richiedono un tempo lineare per inserire o cancellare su una locazione arbitraria, dal momento che tutti gli elementi seguenti devono essere spostati, mentre le liste concatenato possono farlo in tempo costante. Questo svantaggio è mitigato dal buffer gap e dalla variante vettore graduato discusso nel paragrafo Varianti più sotto. Inoltre, per una regione di memoria altamente frammentata, può essere dispendiosa o impossibile trovare uno spazio contiguo per un grosso array dinamico, mentre le liste concatenate non richiedono che l'intera struttura dati sia memorizzata in maniera contigua.

Varianti

I buffer gap sono simili agli array dinamici ma consentono un'efficiente operazioni di inserimento e rimozione raggruppata vicino la stessa locazione arbitraria. Alcune implementazioni di deque utilizzano gli array deque, i quali consentono tempo costante ammortizzato di inserimento/rimozione su entrambe gli estremi, anziché solo alla fine.

Goodrich ha presentato un algoritmo di array dinamici chiamato Tiered Vectors (vettore graduato) che consente prestazioni O(n<sup<1/2) per preservare l'inserimento o la rimozione dal mezzo dell'array.

L'Hashed array tree (HAT) è un algoritmo di array dinamico invetato da Sitarski nel 1996. L'Hashed Array Tree perde una quantità di spazio di memorizzazione nell'ordine di n^1/2, dove n è il numero di elementi nell'array. L'algoritmo ha le prestazioni ammortizzate su O(1) quando aggiunge una serie di oggetti alla fine dell'Hashed Array Tree.

In una relazione del 1999 , Brodnik et al. descrive una struttura dati array graduato dinamico, il quale perde solo n^1/2 di spazio per n elementi in qualsiasi punto nel tempo, e provano un limite più basso mostrando che gli array dinamici devono perdere questo spazio in più se le operazioni sono di rimanere ammortizzate nel tempo. In aggiunta, presentano una variante dove l'allargamento e lo restringimento del buffer non sono solo ammortizati ma nel caso peggiore in tempo costante.

Bagwell (2002) ha presentato l'algoritmo VList, il quale può essere adottato per implementare un array dinamico.

Supporto linguaggio

Il std::vector di C++ è un'implementazione degli array dinamici, cosi come le classi ArrayList fornite con l'API Java e l'infrastruttura .NET. Il classe generica List<> fornita con la versione 2.0 dell'infrastruttura .NET è implementata anche con array dinamici. Il Delphi e il D implementano gli array dinamici nel nucleo (il cosiddetto core) del linguaggio. Molti linguaggi di scripting come il Perl e il PHP offrono gli array dinamici come tipo di dati primitivo built-in.

Riferimenti

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 17.4: Dynamic tables, pp.416–425.

Vedere anche

• Allocazione dinamica della memoria

Collegamenti esterni

• NIST Dictionary of Algorithms and Data Structures: Dynamic array
• VPOOL - C language implementation of dynamic array.

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file su array dinamico