Array dinamico: differenze tra le versioni

spazi
(sistemo un pò)
(spazi)
== 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:
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)
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 [[Notazione O Grande|''O''(''n'')]], ciò significa che ogni inserimento prende un tempo costante [[Analizi ammortizzata|ammortizzato]]. Il
Man mano che gli ''n'' elementi vengono inseriti, le capacità formano una
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.
[[progressione geometrica]]. Espandere l'array di una qualsiasi proporzione
costante assicura che l'inserimento di ''n'' elementi prende un tempo
complessivo di [[Notazione O Grande|''O''(''n'')]], ciò significa che ogni
inserimento prende un tempo costante [[Analizi ammortizzata|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à.
loro dimensione scende sotto una certa soglia, come il 30% della capacità.
 
Gli array dinamici sono un esempio comune quando si insegna [[analisi ammortizzata]].
|}
</div>
L'array dinamico ha prestazioni simili all'array, con l'aggiunta delle nuove operazioni di aggiungere e rimuovere gli elementi dalla fine:
operazioni di aggiungere e rimuovere gli elementi dalla fine:
 
* Ottenere o impostare il valore a un particolare indice (tempo costante)
* 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 [[CPU cache|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
[[località di riferimento]] e l'utilizzo di [[CPU cache|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 [[lista concatenata|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
Paragonati alle [[lista concatenata|liste concatenate]], gli array dinamici
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ù
hanno un'indicizzazione più rapida (tempo costante contro tempo lineare) e
sotto. Inoltre, per una regione di memoria altamente [[Frammentazione|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.
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
[[Frammentazione|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 [[Deque#Implementazioni|array deque]], i quali consentono tempo costante ammortizzato di inserimento/rimozione su entrambe gli estremi, anziché solo alla fine.
operazioni di inserimento e rimozione raggruppata vicino la stessa locazione
arbitraria. Alcune implementazioni di [[deque]] utilizzano gli
[[Deque#Implementazioni|array deque]], i quali consentono tempo costante
ammortizzato di inserimento/rimozione su entrambe gli estremi, anziché solo
alla fine.
 
Goodrich<ref name="tiered_vector">Tiered Vectors: Efficient Dynamic Arrays for
Rank-Based Sequences.[http://citeseer.ist.psu.edu/519744.html]</ref> ha presentato un algoritmo di array dinamici chiamato ''Tiered Vectors'' (vettore graduato) che consente prestazioni O(n<sup<1/2</sup>) per preservare l'inserimento o la rimozione dal mezzo dell'array.
presentato un algoritmo di array dinamici chiamato ''Tiered Vectors'' (vettore
graduato) che consente prestazioni O(n<sup<1/2</sup>) per preservare
l'inserimento o la rimozione dal mezzo dell'array.
 
L'[[Hashed array tree]] (HAT) è un algoritmo di array dinamico inventato da Sitarski nel 1996.<ref name="sitarski96"> HATs: Hashed array trees.[http://www.ddj.com/architect/184409965?pgno=5]</ref> L'Hashed Array Tree perde una quantità di spazio di memorizzazione nell'ordine di n<sup>1/2</sup>, 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.
Sitarski nel 1996.<ref name="sitarski96"> HATs: Hashed array trees.
[http://www.ddj.com/architect/184409965?pgno=5]</ref> L'Hashed Array Tree perde
una quantità di spazio di memorizzazione nell'ordine di n<sup>1/2</sup>, 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 <ref name="brodnik"> Resizable Arrays in Optimal Time