Array dinamico: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m →Supporto linguaggio: Corretto red link |
Nessun oggetto della modifica |
||
Riga 1:
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 (informatica)|libreria]] standard in molti moderni [[linguaggio di programmazione|linguaggi di programmazione]] principali.
Un array dinamico non è la stessa cosa di un array [[allocazione dinamica della memoria|allocato dinamicamente]]: quest'ultimo è un array di dimensione fissata all'atto dell'allocazione o instanziazione dell'array stesso; 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 alla 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, semplicemente, ''dimensione''), mentre la dimensione dell'array sottostante è chiamata la ''capacita'' dell'array dinamico, che è la massima dimensione logica possibile.
Nelle applicazioni
== Espansione geometrica e costo ammortizzato ==
Line 29 ⟶ 25:
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
Gli array dinamici sono un esempio comune quando si insegna [[analisi ammortizzata]].
Line 60 ⟶ 56:
|}
</div>
L'array dinamico ha prestazioni simili all'array, con l'aggiunta delle nuove operazioni di
* Ottenere o impostare il valore a un particolare indice (tempo costante)
Line 67 ⟶ 63:
* 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
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
Line 83 ⟶ 78:
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 and Space.[http://www.cs.uwaterloo.ca/research/tr/1999/09/CS-99-09.pdf]</ref>, Brodnik et al. descrivono una struttura dati array graduato dinamico, il quale perde solo n<sup>1/2</sup> 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 ammortizzati ma nel caso peggiore in tempo costante.
Bagwell (2002)<ref> Fast Functional Lists, Hash-Lists, Deques and Variable Length Arrays.[http://citeseer.ist.psu.edu/bagwell02fast.html] </ref> ha presentato l'algoritmo [[VList]], il quale può essere adottato per implementare un array dinamico.
== Supporto linguaggio ==
| |||