c# - vbnet - visual basic pierotofy




Strutture dati.NET: ArrayList, List, HashTable, Dictionary, SortedList, SortedDictionary-VelocitĂ , memoria e quando usarli? (10)

Strutture dati .NET:

Altro su cui parlare del perché ArrayList e List sono in realtà diversi

Array

Come afferma un utente, gli array sono la raccolta "vecchia scuola" (sì, gli array sono considerati una raccolta anche se non fanno parte di System.Collections ). Ma cos'è la "vecchia scuola" sugli array rispetto ad altre raccolte, ad esempio quelle che hai elencato nel tuo titolo (qui, ArrayList e List (Of T))? Iniziamo con le basi guardando gli array.

Per iniziare, gli Arrays in Microsoft .NET sono "meccanismi che consentono di trattare diversi elementi [correlati logicamente] come una singola 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 sequenzialmente a partire da quell'indirizzo.

Oltre a ciò e contrariamente a programmare 101 concezioni comuni, gli array possono essere davvero complessi:

Gli array possono essere a dimensione singola, multidimensionale o jadded (gli array frastagliati meritano di essere letti). Gli array stessi non sono dinamici: una volta inizializzato, una matrice di n dimensioni 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 0 s). L'indirizzo di questo blocco viene restituito a _array .

Secondo l'articolo, Common Language Specification (CLS) richiede che tutti gli array siano basati su zero. Le matrici in .NET supportano matrici non basate su zero; tuttavia, questo è meno comune. Come risultato della "comunanza" degli array a base zero, Microsoft ha dedicato molto tempo ad ottimizzare le proprie prestazioni ; pertanto, le matrici a dimensione singola, a base zero (SZ) sono "speciali" - e veramente la migliore implementazione di un array (al contrario di multidimensionali, ecc.) - perché le SZ hanno istruzioni specifiche per il linguaggio intermedio per manipolarle.

Gli array vengono sempre passati per riferimento (come indirizzo di memoria) - un pezzo importante del puzzle di Array da sapere. Mentre eseguono il controllo dei limiti (genererà un errore), il controllo dei limiti può essere disabilitato anche sugli array.

Di nuovo, il più grande ostacolo agli array è che non sono ridimensionabili. Hanno una capacità "fissa". Presentazione di ArrayList e List (Of T) nella nostra cronologia:

ArrayList: elenco non generico

L' ArrayList (insieme a List(Of T) - anche se ci sono alcune differenze critiche, qui, spiegate più avanti) - è forse il più pensato come la prossima aggiunta alle collezioni (in senso lato). ArrayList eredita dall'interfaccia IList (discendente di "ICollection"). Le liste di array, da sole, sono bulkier - richiedono più overhead - rispetto a Lists.

IList abilita l'implementazione a trattare le liste di array come elenchi di dimensioni fisse (come gli array); tuttavia, al di là della funzionalità aggiuntiva aggiunta da ArrayList, non ci sono vantaggi reali nell'uso di ArrayList con dimensioni fisse come ArrayList (su Array), in questo caso sono nettamente più lenti.

Dalla mia lettura, ArrayLists non può essere frastagliato: "L'uso di array multidimensionali come elementi ... non è supportato". Di nuovo, un altro chiodo nella bara di ArrayLists. Anche gli ArrayList non sono "tipizzati", il che significa che, al di sotto di tutto, un ArrayList è semplicemente una matrice dinamica di oggetti: Object[] . Ciò richiede un sacco di boxe (implicito) e unboxing (esplicito) quando si implementa ArrayList, aggiungendo di nuovo al proprio overhead.

Pensiero non comprovato: penso di ricordare o di aver letto da uno dei miei professori che ArrayLists è una sorta di bastardo figlio concettuale del tentativo di passare dagli array alle raccolte di tipo elenco, cioè mentre un tempo era stato un grande miglioramento per gli array, non sono più l'opzione migliore in quanto è stato fatto ulteriore sviluppo rispetto alle collezioni

List (Of T): quale ArrayList è diventato (e spero di essere)

La differenza nell'utilizzo della memoria è abbastanza significativa per cui un List (Of Int32) ha consumato il 56% di memoria in meno rispetto a un ArrayList che contiene lo stesso tipo primitivo (8 MB rispetto a 19 MB nella dimostrazione collegata di gentleman sopra: di nuovo, linkato overhead ) - sebbene questo è un risultato aggravato dalla macchina a 64 bit. Questa differenza dimostra davvero due cose: la prima (1), un "oggetto" di tipo Int32 in scatola (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'è una List (Of T) ? MSDN definisce un List(Of T) come "... un elenco fortemente tipizzato di oggetti a cui è possibile accedere per indice". L'importanza qui è il bit "fortemente tipizzato": un List (Of T) "riconosce" tipi e memorizza gli oggetti come loro tipo. Quindi, un Int32 è memorizzato come Int32 e non come un tipo di Object . Questo elimina i problemi causati dal pugilato e dall'unboxing.

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

Essenzialmente, List (Of T) è ArrayList, ma meglio. È l'equivalente generico di ArrayList. Come ArrayList, non è garantito che venga ordinato fino a quando non viene ordinato (vai alla figura). List (Of T) ha anche alcune funzionalità aggiunte.

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

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

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

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

Vi sono altre strutture dati degne di essere menzionate?

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


Ecco alcuni suggerimenti generali per te:

  • È possibile utilizzare foreach su tipi che implementano IEnumerable . IList è essenzialmente un oggetto IEnumberable con Count e Item (accesso agli elementi che utilizzano un indice a base zero). IDictionary d'altra parte significa che puoi accedere agli oggetti con un indice qualsiasi.

  • Array , ArrayList e List all implementano IList . Dictionary , SortedDictionary e Hashtable implementano IDictionary .

  • Se si utilizza .NET 2.0 o versione successiva, si consiglia di utilizzare le controparti generiche dei tipi citati.

  • Per la complessità di tempo e spazio di varie operazioni su questi tipi, è necessario consultare la documentazione.

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

  • Per ottenere una conoscenza approfondita delle strutture dati, consultare risorse come CLRS .


Fuori dalla mia testa:

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

  • ArrayList : array in crescita automatica. Aggiunge ulteriori spese generali. Può enum., Probabilmente più lento di un normale array ma ancora piuttosto veloce. Questi sono usati molto in .NET

  • List - uno dei miei preferiti - può essere usato con generici, quindi puoi avere un array fortemente tipizzato, ad esempio List<string> . Oltre a questo, si comporta molto come ArrayList

  • Hashtable - plain old hashtable. O (1) a O (n) nel peggiore dei casi. È possibile enumerare le proprietà value e keys e le coppie key / val

  • Dictionary - come sopra solo fortemente digitato tramite generici, come Dictionary<string, string>

  • SortedList : un elenco generico ordinato. Rallentato in fase di inserimento dal momento che deve capire dove mettere le cose. Può enum., Probabilmente lo stesso sul recupero in quanto non deve ricorrere, ma la cancellazione sarà più lenta di una semplice vecchia lista.

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

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


Hashtables / Dizionari sono prestazioni O (1), il che significa che le prestazioni non sono una funzione della dimensione. Questo è importante sapere.

EDIT: In pratica, la complessità temporale media per le ricerche Hashtable / Dictionary <> è O (1).


Innanzitutto, tutte le raccolte in .NET implementano IEnumerable.

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

Quindi, anche se le raccolte generiche probabilmente aggiungono funzionalità, per la maggior parte:

  • List è una implementazione generica di ArrayList.
  • Il dizionario è un'implementazione generica di Hashtable

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

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

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

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

Inoltre, LinkedList è un'implementazione standard delle liste collegate (la lista è una lista di array per un recupero più rapido).


Le raccolte generiche avranno prestazioni migliori rispetto alle loro controparti non generiche, soprattutto quando iterano attraverso molti articoli. Questo perché la boxe e l'unboxing non si verificano più.


Sono solidale con la domanda - anch'io ho trovato (trovato?) La scelta sconcertante, quindi ho deciso scientificamente di vedere quale struttura dati è la più veloce (ho fatto il test usando VB, ma immagino che C # sarebbe lo stesso, dal momento che entrambe le lingue fare la stessa cosa a livello di CLR). Qui puoi vedere alcuni risultati di benchmark condotti da me (c'è anche qualche discussione su quale tipo di dati è meglio usare in quali circostanze).


Una nota importante su Hashtable vs Dictionary per ingegneria di trading sistematica ad alta frequenza: Thread Safety Issue

Hashtable è thread-safe per l'utilizzo da più thread. I membri statici del dizionario sono thread-safe, ma non è garantito che tutti i membri dell'istanza siano così.

Quindi Hashtable rimane la scelta "standard" a questo riguardo.


Se possibile, usa i farmaci generici. Ciò comprende:

  • Elenca invece di ArrayList
  • Dizionario invece di HashTable

Strutture e raccolte dati C # più popolari

  • schieramento
  • Lista di array
  • Elenco
  • Lista collegata
  • Dizionario
  • HashSet
  • Pila
  • Coda
  • SortedList

C # .NET ha un sacco di diverse strutture di dati, ad esempio, uno dei più comuni è un array. Tuttavia C # viene fornito con molte più strutture di dati di base. Scegliere la struttura dati corretta da utilizzare è parte della scrittura di un programma ben strutturato ed efficiente.

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

schieramento

La struttura dati forse più semplice e più comune è l'array. AC # array è fondamentalmente un elenco di oggetti. I suoi tratti distintivi 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 veloce agli elementi in base alla loro posizione all'interno dell'elenco (altrimenti noto come indice). AC # array è definito in questo modo:

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

Qualche esempio:

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

Come puoi vedere dall'esempio precedente, 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.

Lista di array

La struttura dati C #, ArrayList, è una matrice dinamica. Ciò significa che un ArrayList può avere qualsiasi quantità di oggetti e di qualsiasi tipo. Questa struttura 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 sono raddoppiate ogni volta che esaurisce lo spazio. Raddoppiare la dimensione dell'array interno è una strategia molto efficace che riduce la quantità di copia degli elementi nel lungo periodo. Non entreremo nella prova di ciò qui. La struttura dei dati è molto semplice da usare:

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

Lo svantaggio della struttura dei dati di ArrayList è che bisogna restituire i valori recuperati nel loro tipo originale:

int arrayListValue = (int)myArrayList[0]

Fonti e ulteriori informazioni che puoi trovare qui :







data-structures