Strutture di dati .NET: ArrayList, List, HashTable, Dictionary, SortedList, SortedDictionary - Velocità, memoria e quando utilizzarle?

Question

.NET ha molte strutture dati complesse. Sfortunatamente, alcuni di loro sono abbastanza simili, e non sono sempre sicuro quando usarne uno e quando usarne un altro. La maggior parte dei miei libri su C # e Visual Basic ne parlano in una certa misura, ma non entrano mai nei dettagli reali.

Qual è la differenza tra Array, ArrayList, List, Hashtable, Dictionary, SortedList e SortedDictionary?

Quali sono enumerabili (IList - può fare cicli 'foreach')? Quali usano coppie chiave / valore (IDict)?

Che dire dell'impronta di memoria? Velocità di inserimento? Velocità di recupero?

Esistono altre strutture di dati degne di nota?

Sto ancora cercando ulteriori dettagli sull'utilizzo della memoria e sulla velocità (notazione Big-O).

Answer 1

In cima alla mia testa:

• Array * - rappresenta un array di memoria di vecchia scuola - un po 'come un alias per un normale array type [] . Può elencare. Non può crescere automaticamente. Assumerei una velocità di inserimento e retrival molto elevata.

• ArrayList - array in crescita automatica. Aggiunge più sovraccarico. Può enum., Probabilmente più lento di un array normale ma comunque piuttosto veloce. Questi sono usati molto in .NET

• Elenco - uno dei miei preferiti - può essere usato con generici, quindi puoi avere un array fortemente tipizzato, ad es. Elenco < stringa > . Oltre a ciò, si comporta in modo molto simile a ArrayList

• Hashtable - semplice vecchia hashtable. Caso peggiore da O (1) a O (n). Può enumerare il valore e le proprietà delle chiavi ed eseguire coppie chiave / val

• Dizionario - lo stesso di cui sopra è tipicamente fortemente tipizzato tramite generici, come Dictionary < string, string >

• SortedList - un elenco generico ordinato. Rallentata all'inserimento poiché deve capire dove collocare le cose. Può enum., Probabilmente lo stesso al momento del recupero poiché non deve ricorrere, ma la cancellazione sarà più lenta di un semplice vecchio elenco.

Tendo sempre a usare List e Dictionary - una volta che inizi a usarli fortemente tipizzati con generici, è davvero difficile tornare allo standard non generico quelli.

Ci sono anche molte altre strutture di dati - c'è KeyValuePair che puoi usare per fare cose interessanti, c'è un SortedDictionary che può essere utile anche.

Answer 2

Se possibile, usa i generici. Questo include:

• Elenco invece di ArrayList
• Dizionario anziché HashTable

Answer 3

Innanzitutto, tutte le raccolte in .NET implementano IEnumerable.

In secondo luogo, molte raccolte sono duplicate perché i generici sono stati aggiunti nella versione 2.0 del framework.

Quindi, sebbene le raccolte generiche probabilmente aggiungano funzionalità, per la maggior parte:

• List è un'implementazione generica di ArrayList.
• Dizionario è un'implementazione generica di Hashtable

Le matrici sono una raccolta di dimensioni fisse che è possibile modificare il valore memorizzato in un determinato indice.

SortedDictionary è un IDictionary che viene ordinato in base alle chiavi. SortedList è un IDictionary che viene ordinato in base a un IComparer richiesto.

Quindi, le implementazioni di IDictionary (quelle che supportano KeyValuePairs) sono: * Hashtable * Dizionario * SortedList * SortedDictionary

Un'altra raccolta che è stata aggiunta in .NET 3.5 è Hashset. È una raccolta che supporta operazioni set.

Inoltre, LinkedList è un'implementazione standard di elenchi collegati (l'elenco è un elenco di array per un recupero più rapido).

Answer 4

Un buon cheat sheet che menziona le complessità per strutture dati, algoritmi, ecc.

Answer 5

Ecco alcuni suggerimenti generali per te:

• Puoi usare foreach su tipi che implementano IEnumerable . IList è essenzialmente un IEnumberable con Count e Item (accesso agli oggetti usando un indice a base zero). IDictionary d'altra parte significa che è possibile accedere agli elementi tramite qualsiasi indice hash.

• Array , ArrayList e List implementano tutti IList . Dizionario , SortedDictionary e Hashtable implementano IDictionary.

• Se si utilizza .NET 2.0 o versioni successive, si consiglia di utilizzare controparti generiche dei tipi citati.

• Per la complessità temporale e spaziale di varie operazioni su questi tipi, è necessario consultare la loro documentazione.

• Le strutture di dati .NET si trovano nello spazio dei nomi System.Collections . Esistono librerie di tipi come PowerCollections che offrono strutture di dati aggiuntive.

• Per una comprensione approfondita delle strutture di dati, consultare risorse come CLRS .

Answer 6

Strutture di dati .NET:

Altro sulla conversazione sul perché ArrayList e List sono effettivamente diversi

Array

Come afferma un utente, gli array sono la "vecchia scuola" raccolta (sì, le matrici sono considerate una raccolta anche se non fanno parte di System.Collections ). Ma cos'è la "vecchia scuola"? sulle matrici rispetto ad altre raccolte, ovvero quelle che hai elencato nel tuo titolo (qui, ArrayList and List (Of T))? Cominciamo dalle basi guardando Array.

Per iniziare, Array in Microsoft .NET sono " ; meccanismi che ti consentono di trattare diversi elementi [logicamente correlati] come un'unica raccolta, " (vedi articolo collegato). Cosa significa? Gli array memorizzano i singoli membri (elementi) in sequenza, uno dopo l'altro in memoria con un indirizzo iniziale. Usando l'array, possiamo facilmente accedere agli elementi memorizzati in sequenza a partire da quell'indirizzo.

Oltre a ciò e contrariamente alla programmazione di 101 concezioni comuni, gli array possono davvero essere piuttosto complessi:

Le matrici possono essere monodimensionali, multidimensionali o jadded (vale la pena leggere le matrici frastagliate). Gli array stessi non sono dinamici: una volta inizializzato, un array di dimensioni n riserva abbastanza spazio per contenere n numero di oggetti. Il numero di elementi nell'array non può aumentare o diminuire. Dim _array As Int32 () = New Int32 (100) riserva abbastanza spazio sul blocco di memoria affinché l'array contenga 100 oggetti di tipo primitivo Int32 (in questo caso, l'array viene inizializzato per contenere 0s). L'indirizzo di questo blocco viene restituito a _array .

Secondo l'articolo, Common Language Specification (CLS) richiede che tutti gli array essere a base zero. Le matrici in .NET supportano matrici non basate su zero; tuttavia, questo è meno comune. Come risultato del "comune" " di array a base zero, Microsoft ha impiegato molto tempo a ottimizzare le proprie prestazioni ; pertanto, gli array a dimensione singola, a base zero (SZ) sono "speciali" - e davvero la migliore implementazione di un array (al contrario del multidimensionale, ecc.) - perché gli SZ hanno specifiche istruzioni linguistiche intermedie per manipolarli.

Le matrici vengono sempre passate per riferimento (come indirizzo di memoria), un pezzo importante del puzzle dell'array da conoscere. Mentre eseguono il controllo dei limiti (genererà un errore), il controllo dei limiti può anche essere disabilitato sugli array.

Ancora una volta, il più grande ostacolo alle matrici è che non sono ridimensionabili. Hanno un "fisso" capacità. Presentazione di ArrayList and List (Of T) alla nostra storia:

ArrayList - elenco non generico

ArrayList (insieme a List (Of T) - anche se ci sono alcune differenze critiche, qui, spiegate più avanti) - è forse meglio pensato come la prossima aggiunta alle collezioni (in senso lato). ArrayList eredita da IList (un discendente di 'ICollection') interfaccia. Gli stessi array sono bulkier - che richiedono più overhead - rispetto agli elenchi.

IList consente all'implementazione di trattare ArrayLists come elenchi di dimensioni fisse (come gli array); tuttavia, al di là della funzionalità aggiuntiva aggiunta da ArrayLists, non vi sono reali vantaggi nell'uso di ArrayList di dimensioni fisse poiché ArrayLists (su Array) in questo caso sono notevolmente più lenti.

Dalla mia lettura, ArrayLists non può essere frastagliato: " L'uso di array multidimensionali come elementi ... non è supportato " ;. Ancora una volta, un altro chiodo nella bara di ArrayLists. Anche gli ArrayLists non sono "digitati" - significa che, sotto ogni cosa, un ArrayList è semplicemente un array dinamico di oggetti: Object [] . Ciò richiede un sacco di boxe (implicito) e unboxing (esplicito) durante l'implementazione di ArrayLists, aggiungendo di nuovo al loro overhead.

Pensiero non comprovato: penso di ricordare di aver letto o di aver sentito da uno dei miei professori che ArrayLists è una specie di figlio concettuale bastardo del tentativo di passare da Array a Collezioni di tipo List, ovvero mentre una volta un grande miglioramento per gli array, non sono più l'opzione migliore poiché sono stati fatti ulteriori sviluppi rispetto alle collezioni

Elenco (di T): ciò che ArrayList è diventato (e sperava di essere)

La differenza nell'uso della memoria è abbastanza significativa da dove una Lista (Of Int32) ha consumato il 56% di memoria in meno rispetto a una ArrayList contenente lo stesso tipo primitivo (8 & nbsp; MB vs. 19 & nbsp; MB nella dimostrazione collegata del gentiluomo sopra: di nuovo, collegato qui ) - sebbene questo sia un risultato aggravato dalla macchina a 64 bit. Questa differenza dimostra davvero due cose: primo (1), un oggetto di tipo Int32 inscatolato "oggetto". (ArrayList) è molto più grande di un puro tipo primitivo Int32 (Elenco); secondo (2), la differenza è esponenziale a causa del funzionamento interno di una macchina a 64 bit.

Quindi, qual è la differenza e cos'è un Elenco (Of T) ? MSDN definisce un List (Of T) as, " ;. .. un elenco fortemente tipizzato di oggetti a cui è possibile accedere tramite indice. " L'importanza qui è la "quotazione fortemente tipizzata" bit: un elenco (di T) "riconosce" i tipi e memorizza gli oggetti come tipo. Pertanto, un Int32 viene archiviato come un Int32 e non un tipo Object . Questo elimina i problemi causati da boxe e unboxing.

MSDN specifica che questa differenza entra in gioco solo quando si memorizzano tipi primitivi e non tipi di riferimento. Troppo, la differenza si verifica in realtà su larga scala: oltre 500 elementi. La cosa più interessante è che la documentazione MSDN recita, " È a tuo vantaggio usare l'implementazione specifica del tipo della classe List (Of T) invece di usare la classe ArrayList .... "

In sostanza, List (Of T) è ArrayList, ma migliore. È l'equivalente "generico" di ArrayList. Come ArrayList, non è garantito che vengano ordinati fino a quando non vengono ordinati (vai alla figura). List (Of T) ha anche alcune funzionalità aggiunte.

Answer 7

Sono d'accordo con la domanda: anch'io ho trovato (trovare?) sconcertante la scelta, quindi ho deciso scientificamente di vedere quale struttura di dati è la più veloce (ho fatto il test usando VB, ma immagino che C # sarebbe lo stesso, poiché entrambe le lingue fanno la stessa cosa a livello di CLR). Puoi vedere alcuni risultati di benchmarking da me condotti qui (c'è anche qualche discussione su quale tipo di dati è meglio usare in quali circostanze).

Answer 8

Sono spiegati abbastanza bene in intellisense. Digita System.Collections. o System.Collections.Generics (preferito) e otterrai un elenco e una breve descrizione di ciò che è disponibile.

Answer 9

Hashtables / Dictionaries sono prestazioni O (1), il che significa che le prestazioni non sono una funzione delle dimensioni. È importante saperlo.

EDIT: in pratica, la complessità temporale media di Hashtable / Dictionary < > la ricerca è O (1).

Answer 10

Le raccolte generiche avranno prestazioni migliori rispetto alle loro controparti non generiche, soprattutto quando si ripetono molti elementi. Questo perché non si verificano più boxe e unboxing.

Answer 11

Una nota importante su Hashtable vs Dictionary per l'ingegneria commerciale sistematica ad alta frequenza: Thread Safety Issue

Hashtable è thread-safe per l'uso da parte di più thread. I membri statici pubblici del dizionario sono thread-safe, ma non è garantito che tutti i membri di istanza lo siano.

Quindi Hashtable rimane la scelta 'standard' in questo senso.

Answer 12

Esistono differenze sottili e non così sottili tra raccolte generiche e non generiche. Utilizzano semplicemente diverse strutture di dati sottostanti. Ad esempio, Hashtable garantisce uno scrittore-molti-lettori senza sincronizzazione. Dizionario no.

Answer 13

In realtà, penso che MSDN aiuta a fornire risposte piuttosto valide a tutte queste domande. Cerca le raccolte .NET.

Answer 14

Strutture e raccolte di dati C # più popolari

• Array
• ArrayList
• Elenco
• LinkedList
• dizionario
• HashSet
• Stack
• Coda
• SortedList

C # .NET ha molte strutture dati diverse, ad esempio una delle più comuni è una matrice. Tuttavia, C # include molte più strutture di dati di base. La scelta della struttura dati corretta da utilizzare fa parte della stesura di un programma ben strutturato ed efficiente.

In questo articolo esaminerò le strutture di dati C # integrate, comprese le nuove introdotte in C # .NET 3.5. Si noti che molte di queste strutture dati si applicano ad altri linguaggi di programmazione.

Array

La struttura dei dati forse più semplice e più comune è l'array. Un array C # è fondamentalmente un elenco di oggetti. Le sue caratteristiche distintive sono che tutti gli oggetti sono dello stesso tipo (nella maggior parte dei casi) e ne esiste un numero specifico. La natura di un array consente un accesso molto rapido agli elementi in base alla loro posizione all'interno dell'elenco (altrimenti noto come indice). Un array C # è definito in questo modo:

[object type][] myArray = new [object type][number of elements]

Alcuni esempi:

 int[] myIntArray = new int[5];
 int[] myIntArray2 = { 0, 1, 2, 3, 4 };

Come puoi vedere dall'esempio sopra, un array può essere inizializzato senza elementi o da un insieme di valori esistenti. L'inserimento di valori in un array è semplice purché si adattino. L'operazione diventa costosa quando ci sono più elementi della dimensione dell'array, a quel punto l'array deve essere espanso. Questo richiede più tempo perché tutti gli elementi esistenti devono essere copiati nel nuovo array più grande.

ArrayList

La struttura di dati C #, ArrayList, è un array dinamico. Ciò significa che un ArrayList può avere qualsiasi quantità di oggetti e di qualsiasi tipo. Questa struttura di dati è stata progettata per semplificare i processi di aggiunta di nuovi elementi in un array. Sotto il cofano, un ArrayList è un array le cui dimensioni vengono raddoppiate ogni volta che si esaurisce lo spazio. Raddoppiare le dimensioni dell'array interno è una strategia molto efficace che riduce la quantità di elementi copiati nel lungo periodo. Non entreremo nella prova di questo qui. La struttura dei dati è molto semplice da usare:

    ArrayList myArrayList = new ArrayList();
    myArrayList.Add(56);
    myArrayList.Add("String");
    myArrayList.Add(new Form());

Il rovescio della medaglia della struttura di dati ArrayList è che bisogna riportare i valori recuperati nel loro tipo originale:

int arrayListValue = (int)myArrayList[0]

Fonti e altre informazioni che puoi trovare qui :

• Strutture dati C #
• Collezioni e strutture di dati
• Elenco vs IEnumerable vs IQueryable vs ICollection vs IDictionary
• System.Collections. Spazio dei nomi generico
• Spazio dei nomi System.Collections