Array dinamico: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
sistemo un pò |
spazi |
||
Riga 17:
== 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)
Line 30 ⟶ 27:
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
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]].
Line 72 ⟶ 61:
|}
</div>
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)
Line 80 ⟶ 68:
* 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
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
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.
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.
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.▼
▲ammortizzate su O(1) quando aggiunge una serie di oggetti alla fine dell'Hashed
In una relazione del 1999 <ref name="brodnik"> Resizable Arrays in Optimal Time
| |||