.NET-Datenstrukturen:ArrayList, List, HashTable, Dictionary, SortedList, SortedDictionary – Geschwindigkeit, Speicher und wann jeweils zu verwenden?

https://stackoverflow.com/questions/128636

02-07-2019
|

Frage

.NET verfügt über viele komplexe Datenstrukturen.Leider sind einige davon ziemlich ähnlich und ich bin mir nicht immer sicher, wann ich das eine und wann das andere verwenden soll.In den meisten meiner C#- und Visual Basic-Bücher geht es bis zu einem gewissen Grad darum, aber sie gehen nie wirklich ins Detail.

Was ist der Unterschied zwischen Array, ArrayList, List, Hashtable, Dictionary, SortedList und SortedDictionary?

Welche sind aufzählbar (IList – kann „foreach“-Schleifen ausführen)?Welche verwenden Schlüssel/Wert-Paare (IDict)?

Wie sieht es mit dem Speicherbedarf aus?Einfügegeschwindigkeit?Abrufgeschwindigkeit?

Gibt es weitere erwähnenswerte Datenstrukturen?

Ich suche immer noch nach weiteren Details zur Speichernutzung und Geschwindigkeit (Big-O-Notation).

Lösung

Aus dem Kopf heraus:

Array* – stellt ein Speicherarray der alten Schule dar – eine Art Alias für ein normales type[] Array.Kann aufzählen.Kann nicht automatisch wachsen.Ich gehe von einer sehr schnellen Einfüge- und Abrufgeschwindigkeit aus.
ArrayList - Automatisch wachsendes Array.Fügt mehr Overhead hinzu.Kann aufzählen, wahrscheinlich langsamer als ein normales Array, aber immer noch ziemlich schnell.Diese werden häufig in .NET verwendet
List - einer meiner Favoriten - kann mit Generika verwendet werden, sodass Sie ein stark typisiertes Array haben können, z. B. List<string>.Ansonsten verhält es sich sehr ähnlich ArrayList
Hashtable - einfache alte Hashtabelle.O(1) bis O(n) schlimmster Fall.Kann die Wert- und Schlüsseleigenschaften aufzählen und Schlüssel/Wert-Paare erstellen
Dictionary - wie oben, nur stark typisiert über Generika, wie z Dictionary<string, string>
SortedList - eine sortierte generische Liste.Verlangsamt sich beim Einsetzen, da es herausfinden muss, wo Dinge abgelegt werden sollen.Kann enum., wahrscheinlich das Gleiche beim Abrufen, da keine Umsortierung erforderlich ist, aber das Löschen ist langsamer als bei einer einfachen alten Liste.

Ich neige dazu, zu verwenden List Und Dictionary ständig - wenn man erst einmal damit beginnt, sie stark typisiert mit Generika zu verwenden, ist es wirklich schwierig, zu den standardmäßigen, nicht generischen Typisierungen zurückzukehren.

Es gibt auch viele andere Datenstrukturen KeyValuePair mit dem Sie einige interessante Dinge tun können, gibt es eine SortedDictionary was auch nützlich sein kann.

Andere Tipps

Wenn möglich, verwenden Sie Generika Dazu gehören:.

Liste anstelle von Arraylist
Wörterbuch statt HashTable

Zuerst werden alle Sammlungen in .NET implementieren IEnumerable.

Zweitens sind viele der Sammlungen sind Duplikate, weil Generika in der Version 2.0 des Rahmens hinzugefügt wurden.

So, obwohl die allgemeinen Sammlungen wahrscheinlich Funktionen hinzufügen, zum größten Teil:

Liste ist eine allgemeine Implementierung von Arraylist.
Wörterbuch ist eine generische Implementierung von Hashtable

Arrays sind eine feste Größe Sammlung, die Sie den Wert zu einem gegebenen Index gespeichert ändern können.

SortedDictionary ist ein IDictionary, die auf den Tasten basierend sortiert ist. SortedList ist ein IDictionary, die auf einem erforderlichen IComparer basierend sortiert wird.

Also, die IDictionary-Implementierungen (die Unterstützung KeyValuePairs) sind: * Hash-tabelle * Wörterbuch * SortedList * SortedDictionary

Eine weitere Sammlung, die .NET 3.5 wurde hinzugefügt in der Hashset. Es ist eine Sammlung, die Set-Operationen unterstützt.

Auch die LinkedList eine Standard-linked-Liste-Implementierung (die Liste ist ein Array-Liste ermöglicht einen schnelleren Abruf).

Ein guter Spickzettel die Komplexität für die Datenerwähnensstrukturen, Algorithmen, etc.

Hier sind ein paar allgemeinen Tipps für Sie:

Sie können foreach auf Typen verwenden, die IEnumerable implementieren. IList ist im Wesentlichen ein IEnumberable mit Count und Item (Zugriff auf Artikel A auf Null basierenden Index verwendet) Eigenschaften aufweisen. IDictionary auf der anderen Seite bedeutet, dass Sie Artikel von jedem-hashable Index zugreifen können.
Array, ArrayList und List alle IList implementieren. Dictionary, SortedDictionary und Hashtable IDictionary implementieren.
Wenn Sie .NET 2.0 oder höher verwenden, ist es empfehlenswert, dass Sie generische Pendants der genannten Typen verwendet werden.
Für Zeit und Raum Komplexität verschiedener Operationen auf diese Art, sollten Sie ihre Dokumentation.
.NET-Datenstrukturen sind in System.Collections Namespace. Es gibt Typbibliotheken wie PowerCollections die Strukturen zusätzliche Daten bieten.
Um ein gründliches Verständnis der Datenstrukturen zu erhalten, konsultieren Ressourcen wie CLRS .

.NET-Datenstrukturen:

Mehr zum Gespräch darüber, warum Arraylist und Liste ist tatsächlich verschiedene

Arrays

Als ein Benutzerstatus, Arrays die „alte Schule“ Sammlung ist (ja, ist Arrays eine Sammlung betrachtet, obwohl nicht Teil System.Collections). Aber, was ist „alten Schule“ über Arrays im Vergleich zu anderen Sammlungen, das heißt die, die Sie in Ihrem Titel aufgeführt haben (hier Arraylist und List (Of T))? Lassen Sie sich mit den Grundlagen beginnen, indem du Arrays suchen.

starten, Arrays in Microsoft .NET ist " Mechanismen, die Sie mehr [logisch bezogene] Artikel als eine einzige Sammlung“(siehe verlinkte Artikel) behandeln lassen. Was bedeutet das? Arrays speichern einzelnen Elemente (Elemente) nacheinander, eine nach der anderen in dem Speicher mit einer Startadresse. Durch das Array verwenden, können wir leicht die sequentiell gespeicherten Elemente an dieser Adresse beginnend zuzugreifen.

Darüber hinaus werden und im Gegensatz zu Programmierung 101 gemeinsamen Vorstellungen, Arrays wirklich kann recht komplex sein:

Arrays können einzelne Dimension, multidimensionale oder jadded sein (gezackt Arrays sind lesenswert über). Arrays selbst sind nicht dynamisch: einmal initialisiert, ein Array von n Größe Reserven genügend Platz zu halten n Anzahl der Objekte. Die Anzahl der Elemente in dem Array kann nicht wachsen oder schrumpfen. Dim _array As Int32() = New Int32(100) Reserven genügend Platz auf dem Speicherblock für das Array 100 enthalten Int32 Urtyp Objekte (in diesem Fall wird das Array initialisiert 0s enthalten). Die Adresse dieses Blocks wird zurückgegeben _array.

Laut dem Artikel, Common Language Specification (CLS) verlangt, dass alle Arrays Null-basiert. Arrays in .NET-Unterstützung nicht-Null-Basis-Arrays; Dies ist jedoch weniger häufig. Als Ergebnis der „common-ness“ von Null-basiertem Arrays hat Microsoft verbringt eine Menge Zeit, ihre Leistung zu optimieren ; also eindimensional, Null-basierte (SZS) Arrays sind „Spezial“ - und wirklich die beste Implementierung eines Arrays (im Gegensatz zu mehrdimensionalen Gegensatz usw.) - weil SZS spezifische Vermittlungssprache Anweisungen haben für sie zu manipulieren.

Arrays werden immer als Referenz (als Speicheradresse) übergeben - ein wichtiges Stück des Array-Puzzle zu kennen. Obwohl sie Grenzen tun Überprüfung (wirft einen Fehler), kann die Überprüfung der Grenzen auch auf Arrays deaktiviert werden.

Auch hier ist das größte Hindernis für Arrays, dass sie nicht wieder ansehnliche sind. Sie haben eine „feste“ Kapazität. Die Einführung Arraylist und List (Of T) zu unserer Geschichte:

Arraylist - nicht-generische Liste

Die Arraylist (zusammen mit List(Of T) - obwohl es einigen kritischen Unterschieden sind, hier später erklärt) - Gedanke ist vielleicht am besten als die nächste neben Sammlungen (im weitesten Sinne). Arraylist erben von der IList (ein Nachkomme von 'ICollection') Schnittstelle. Arraylisten, selbst, sind sperriger - erfordert mehr Kopf - als Listen.

IList funktioniert die Implementierung ermöglichen Arraylisten als feste Größe Listen (wie Arrays) zu behandeln; jedoch über den zusätzlichen functionallity von Arraylists hinzugefügt, gibt es keine wirklichen Vorteile bei der Verwendung Arraylisten, die eine feste Größe werden als Arraylisten (über Arrays) sind in diesem Fall deutlich langsamer.

Aus meiner Lektüre können Arraylisten nicht gezackt sein: „Multidimension verwendenal-Arrays als Elemente ... wird nicht unterstützt“Wieder ein anderer Nagel in den Sarg der Arraylisten Arraylists sind auch nicht..‚getippt‘- was bedeutet, dass, unter allem, eine Arraylist ist einfach ein dynamisches Array von Objekten. Object[] Dies erfordert eine Menge von Boxen (implizite) und Unboxing (explizit), wenn Arraylisten Umsetzung wieder in ihre Overhead hinzuzufügen.

unbegründete Gedanken: Ich glaube, ich erinnere mich entweder zum Lesen oder von einem meiner Professoren gehört zu haben, die Arraylisten Art des Bastard konzeptionellen Kindes des Versuchs sind von Arrays zu bewegen zur Liste-Art Collections, dh während einmal gewesen eine große Verbesserung zu Arrays, sie sind nicht mehr die beste Option, da die weitere Entwicklung in Bezug auf Sammlungen

getan wurde,

List (Of T): Was wurde Arraylist (und hoffte, dass zu sein)

Der Unterschied in der Speichernutzung ist signifikant genug, um, wo eine List (Of Int32) verbrauchen 56% weniger Speicher als eine Arraylist den gleichen primitiven Typen enthält (8 MB vs. 19 MB in dem verknüpften Demonstration oben Gentleman: wieder, verbunden < a href = "http://blogs.msdn.com/b/joshwil/archive/2004/04/13/112598.aspx" rel = "nofollow noreferrer"> hier ) - obwohl dies ein Ergebnis ist zusammengesetzt durch die 64-Bit-Maschine. Dieser Unterschied zeigt wirklich zwei Dinge: Erstens (1), ein boxed Int32-Typ „Objekt“ (Arraylist) ist viel größer als ein reiner Int32 Urtyp (List); zweite (2), die Differenz exponentielle als Ergebnis der inneren Funktionsweise einer 64-Bit-Maschine.

Also, was ist der Unterschied und was ist ein List (Of T) ? MSDN eine List(Of T) als“definiert ... eine stark typisierte Liste von Objekten, auf die zugegriffen werden kann durch den Index.“ Die Bedeutung ist hier der „stark typisierte“ Bit: eine List (Of T) ‚erkennt‘ Typen und speichert die Objekte als ihre Art. So wird ein Int32 als Int32 gespeichert und nicht ein Object Typ. Dies beseitigt die Probleme verursacht durch Boxen und Unboxing.

MSDN gibt diese Differenz nur dann ins Spiel kommt, wenn primitive Typen zu speichern und nicht Typen verweisen Too, wirklich der Unterschied tritt in großem Maßstab. Über 500 Elemente. Was ist interessanter ist, dass die MSDN-Dokumentation liest, „es zu Ihrem Vorteil ist es, die typspezifische Implementierung der List (Of T) -Klasse zu verwenden, anstatt die Klasse Arraylist verwenden ....“

Im Wesentlichen List (Of T) ist Arraylist, aber besser. Es ist die „generische Äquivalent“ von Arraylist. Wie Arraylist, ist es nicht sortiert werden garantiert bis sortiert (Abbildung gehen). List (Of T) auch hat einige zusätzliche Funktionen.

ich mit der Frage sympathisieren - ich auch gefunden (? Finden) die Auswahl verwirrend, so dass ich wissenschaftlich aus, um zu sehen, welche Datenstruktur ist der schnellste (ich den Test tat VB, aber ich glaube, C # die gleiche sein würde, da beide Sprachen die gleiche Sache auf der CLR-Ebene). Sie können sehen, einige Benchmark-Ergebnisse von mir durchgeführt hier (es gibt auch einige Diskussionen, von denen Datentyp unter welchen Umständen verwenden, am besten ist).

Sie sind ziemlich gut in intellisense buchstabiert. Geben Sie einfach System.Collections. oder System.Collections.Generics (bevorzugt) und Sie erhalten eine Liste und kurze Beschreibung von dem, was verfügbar ist.

Hashtables / Wörterbücher sind O (1) Leistung, was bedeutet, dass die Leistung nicht eine Funktion der Größe ist. Das ist wichtig zu wissen.

EDIT:. In der Praxis ist die durchschnittliche Zeitkomplexität für Hashtable / Dictionary <> Lookups ist O (1)

Die generischen Sammlungen werden besser abschneiden als ihre nicht-generischen Kollegen, vor allem, wenn sie durch viele Elemente iterieren. Dies liegt daran, Boxen und Unboxing nicht mehr auftritt.

Ein wichtiger Hinweis über Hashtable vs Wörterbuch Hochfrequenz systematischer Handelstechnik: Threadsicherheit Ausgabe

Hashtable ist Thread sicher für die Verwendung durch mehrere Threads. Wörterbuch public static Mitglieder sind Thread-sicher, aber alle Instanz Mitglieder garantiert nicht so sein.

So Hashtable die 'Standard' Wahl in dieser Hinsicht bleibt.

Es gibt subtile und nicht-so-subtile Unterschiede zwischen Generika und nicht-generischen Sammlungen. Sie nutzen nur verschiedene zugrunde liegende Datenstrukturen. Zum Beispiel garantiert Hashtable ein Schriftsteller-many-Leser ohne Synchronisation. Wörterbuch nicht.

Eigentlich denke, ich MSDN bieten hilft ziemlich gute Antworten auf all diese Fragen. schauen Sie einfach .NET Sammlungen.

Die beliebtesten C#-Datenstrukturen und -Sammlungen

Array
Anordnungsliste
Aufführen
LinkedList
Wörterbuch
HashSet
Stapel
Warteschlange
SortedList

C#.NET hat viele verschiedene Datenstrukturen, eine der häufigsten ist beispielsweise ein Array.C# verfügt jedoch über viele weitere grundlegende Datenstrukturen.Die Auswahl der richtigen Datenstruktur gehört zum Schreiben eines gut strukturierten und effizienten Programms.

In diesem Artikel werde ich auf die integrierten C#-Datenstrukturen eingehen, einschließlich der neuen, die in C#.NET 3.5 eingeführt werden.Beachten Sie, dass viele dieser Datenstrukturen auch für andere Programmiersprachen gelten.

Array

Die vielleicht einfachste und gebräuchlichste Datenstruktur ist das Array.Ein C#-Array ist im Grunde eine Liste von Objekten.Seine charakteristischen Merkmale sind, dass alle Objekte (in den meisten Fällen) vom gleichen Typ sind und es eine bestimmte Anzahl von ihnen gibt.Die Art eines Arrays ermöglicht einen sehr schnellen Zugriff auf Elemente basierend auf ihrer Position innerhalb der Liste (auch als Index bezeichnet).Ein C#-Array ist wie folgt definiert:

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

Einige Beispiele:

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

Wie Sie dem obigen Beispiel entnehmen können, kann ein Array ohne Elemente oder aus einer Reihe vorhandener Werte initialisiert werden.Das Einfügen von Werten in ein Array ist einfach, solange sie passen.Der Vorgang wird kostspielig, wenn mehr Elemente als die Größe des Arrays vorhanden sind und das Array dann erweitert werden muss.Dies dauert länger, da alle vorhandenen Elemente in das neue, größere Array kopiert werden müssen.

Anordnungsliste

Die C#-Datenstruktur ArrayList ist ein dynamisches Array.Das bedeutet, dass eine ArrayList eine beliebige Anzahl von Objekten und einen beliebigen Typ enthalten kann.Diese Datenstruktur wurde entwickelt, um das Hinzufügen neuer Elemente zu einem Array zu vereinfachen.Unter der Haube ist eine ArrayList ein Array, dessen Größe sich jedes Mal verdoppelt, wenn der Speicherplatz knapp wird.Die Verdoppelung der Größe des internen Arrays ist eine sehr effektive Strategie, die auf lange Sicht den Umfang des Kopierens von Elementen reduziert.Auf den Beweis dafür gehen wir hier nicht näher ein.Die Datenstruktur ist sehr einfach zu verwenden:

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

Der Nachteil der ArrayList-Datenstruktur besteht darin, dass die abgerufenen Werte wieder in ihren ursprünglichen Typ umgewandelt werden müssen:

int arrayListValue = (int)myArrayList[0]

Quellen und weitere Informationen finden Sie hier :

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow