Matrice che può essere ridimensionata rapidamente

Question

Sto cercando un tipo di array di tipo di dati che possa facilmente aggiungere elementi, senza un impatto sulle prestazioni.

• Sistema. Array - Redim Preserve copia l'intera RAM dalla vecchia alla nuova, lenta quanto la quantità di elementi esistenti
• System.Collections. ArrayList - abbastanza buono?
• System.Collections. IList - abbastanza buono?

Answer 1

Solo per riassumere alcune strutture di dati:

System.Collections.ArrayList : le strutture di dati non tipizzate sono obsolete. Usa invece List (of t).

System.Collections.Generic.List (of t) : rappresenta un array ridimensionabile. Questa struttura di dati utilizza un array interno dietro le quinte. L'aggiunta di elementi all'elenco è O (1) purché l'array sottostante non sia stato riempito, altrimenti O (n + 1) per ridimensionare l'array interno e copiarne gli elementi.

List<int> nums = new List<int>(3); // creates a resizable array
                                   // which can hold 3 elements

nums.Add(1);
// adds item in O(1). nums.Capacity = 3, nums.Count = 1

nums.Add(2);
// adds item in O(1). nums.Capacity = 3, nums.Count = 3

nums.Add(3);
// adds item in O(1). nums.Capacity = 3, nums.Count = 3

nums.Add(4);
// adds item in O(n). Lists doubles the size of our internal array, so
// nums.Capacity = 6, nums.count = 4

L'aggiunta di elementi è efficace solo quando si aggiunge in fondo all'elenco. L'inserimento nel mezzo forza l'array a spostare tutti gli elementi in avanti, che è un'operazione O (n). Anche l'eliminazione degli elementi è O (n), poiché l'array deve spostare gli oggetti all'indietro.

System.Collections.Generic.LinkedList (of t) : se non hai bisogno di un accesso casuale o indicizzato agli elementi nel tuo elenco, ad esempio prevedi di aggiungere solo elementi e iterare dal primo per durare, allora un LinkedList è tuo amico. Inserti e rimozioni sono O (1), la ricerca è O (n).

Answer 2

Dovresti usare l'Elenco generico < > ( System.Collections.Generic.List ) per questo. Funziona in tempo ammortizzato costante .

Condivide anche le seguenti funzionalità con le matrici.

• Accesso casuale rapido (puoi accedere a qualsiasi elemento dell'elenco in O (1))
• È veloce passare in rassegna
• Lento per inserire e rimuovere oggetti all'inizio o al centro (dal momento che deve fare una copia dell'intero elenco credenziale)

Se sono necessari inserimenti rapidi ed eliminazioni all'inizio o alla fine, utilizzare l'elenco collegato o le code

Answer 3

Sarebbe il LinkedList < T gt &; la struttura funziona per te? Non è (in alcuni casi) intuitivo come un array semplice, ma è molto veloce.

• AddLast da aggiungere alla fine
• AddBefore / AddAfter da inserire nell'elenco
• AddFirst da aggiungere all'inizio

Tuttavia, non è così rapido per un accesso casuale, poiché devi scorrere la struttura per accedere ai tuoi elementi ... tuttavia, ha metodi .ToList () e .ToArray () per prendere una copia della struttura nell'elenco / array form in modo da poter accedere in lettura in un pizzico. L'aumento delle prestazioni degli inserti può superare la riduzione delle prestazioni della necessità di un accesso casuale o no. Dipenderà interamente dalla tua situazione.

C'è anche questo riferimento che ti aiuterà a decidere qual è la strada giusta da percorrere:

Quando utilizzare un elenco collegato su un elenco di array / array?

Answer 4

Che cos'è " abbastanza buono " per te? Cosa vuoi fare esattamente con quella struttura di dati?

Nessuna struttura di array (ovvero accesso O (n)) consente l'inserimento nel mezzo senza un runtime O (n); l'inserimento alla fine è O (n) nel peggiore dei casi un O (1) ammortizzato per array auto-ridimensionanti come ArrayList.

Forse gli hashtabili (accesso O (1) ammortizzato ovunque e inserimento ovunque, ma O (n) nel caso peggiore per l'inserimento) o alberi (O (log (n)) per accesso e inserimento ovunque, garantiti) sono più adatti.

Answer 5

Se la velocità è il tuo problema, non vedo come la risposta selezionata sia migliore dell'uso di un array non elaborato, anche se si ridimensiona da solo, utilizza lo stesso meccanismo che useresti per ridimensionare un array (e dovrebbe prendere solo un tocco in più) A MENO che non si aggiunga sempre alla fine, nel qual caso dovrebbe fare le cose un po 'più intelligenti perché alloca un pezzo alla volta invece di un solo elemento.

Se aggiungi spesso vicino all'inizio / metà della tua raccolta e non indicizzi molto spesso la metà / fine, probabilmente vorrai un Elenco collegato. Avrà il tempo di inserimento più veloce e avrà un tempo di iterazione eccezionale, fa solo schifo all'indicizzazione (come guardare il terzo elemento dalla fine o il 72 ° elemento).