Wörterbuch vs Liste

30

Also bin ich Dictionary<int, int>heute auf der Arbeit gestoßen. Das kam mir einfach komisch vor, weil ich wahrscheinlich List<int>stattdessen einfach eine verwendet hätte. Gibt es einen Unterschied und würde es einen Anwendungsfall geben, bei dem eine Struktur der anderen vorgezogen würde?

ZeroDivide
quelle
1
Muss es eine Beziehung zwischen zwei (oder mehr) gegebenen Ints geben? Dann macht die Karte (Wörterbuch in dieser Sprache) Sinn.
Rig
3
Das Namenswörterbuch macht es mir klar. Wenn Sie schnell etwas nachschlagen müssen, verwenden Sie ein Wörterbuch.
ChaosPandion
2
@ChaosPandion: a List<T>innerhalb von .NET Framework ist ein Array mit wahlfreiem Zugriff, bei dem ein Suchvorgang normalerweise schneller ist als bei a Dictionary<int,T>.
Doc Brown
2
@DocBrown - Nur in dem etwas seltsamen Fall, dass der numerische Index als Schlüssel verwendet wird. Andernfalls wird das Nachschlagen bei der Verwendung schneller Dictionary<TKey, TValue>.
ChaosPandion
2
@chaos diese Frage handelt von diesem seltsamen Fall.
MarkJ

Antworten:

32

Sie würden a verwenden, Dictionary<int, int>wenn Ihre Indizes neben der Positionsplatzierung eine besondere Bedeutung haben.

Das unmittelbare Beispiel, das mir in den Sinn kommt, ist das Speichern einer ID-Spalte und einer Int-Spalte in einer Datenbank. Wenn Sie zum Beispiel eine [person-id]Spalte und eine [personal-pin]Spalte haben, können Sie diese in a bringen Dictionary<int, int>. Auf diese Weise erhalten pinDict[person-id]Sie eine PIN, aber der Index ist aussagekräftig und nicht nur eine Position in a List<int>.

Aber wenn Sie zwei zusammengehörige Listen mit ganzen Zahlen haben, könnte dies eine geeignete Datenstruktur sein.

Kris Harper
quelle
Wenn meine Personen-ID im Bereich 0, ..., 999 liegt und ich die persönlichen PIN-Werte für alle 1000 Personen in den Speicher laden müsste, würde ich normalerweise ein List<int>und kein Wörterbuch auswählen . Siehe meine Antwort unten.
Doc Brown
3
ja, aber ein Wörterbuch kann spärlich sein
jk.
@jk: genau das habe ich in meiner antwort versucht auszuarbeiten.
Doc Brown
7
Persönliche PIN? Klingt irgendwie überflüssig.
Jack
Hm, wenn der Index "eine besondere Bedeutung" hat, kann es in realen Szenarien wahrscheinlich sein, dass sie keinen zusammenhängenden Bereich [0, ..., n] bilden (obwohl dies nicht obligatorisch ist) nicht einfach falsch, aber ungenau. Dennoch sollte die Entscheidung meiner Meinung nach nicht auf dieser "besonderen Bedeutung" beruhen, sondern nur auf "Bauen die Schlüssel ungefähr ein Intervall [0, ..., n] auf". Aufgrund der Anzahl der positiven Stimmen haben wohl die meisten Leser diesen Punkt verpasst.
Doc Brown
28

Stellen Sie sich das Listals Array und das Dictionaryals Hash-Tabelle vor . Sie würden nur dann verwenden, Dictionarywenn Sie aussagekräftige Schlüssel zu Werten zuordnen List(oder zuordnen) müssten , wohingegen nur Positionen (oder Indizes) zu Werten zugeordnet werden.

Angenommen, Sie möchten eine Zuordnung zwischen dem Alter und der Körpergröße einer Person speichern. Sie können a verwenden Dictionary<int, int>, um das Alter (an int) der Person auf ihre Größe (an int) abzubilden :

Dictionary<int, int> personHeightMap = new Dictionary<int, int>();

personHeightMap.Add(21, 185);
personHeightMap.Add(31, 174);

int height = personHeightMap.ContainsKey(21) ? personHeightMap[21] : -1;

Kein sehr nützliches Beispiel, aber der Punkt ist, dass Sie dies nicht so elegant mit einem tun können, Listweil es diese Werte positionell speichern müsste.

Bernard
quelle
7
+1 für die eine Erwähnung Listmit Angebote um , wo eine Dictionarybefasst sich mit Verband . Wenn Sie Ihre Daten jedes Mal in einer bestimmten Reihenfolge abrufen müssen oder die Reihenfolge in Bezug aufeinander wichtig ist, Listist a der richtige Weg. Dictionariesneigen dazu, ungeordnet zu sein, und beschäftigen sich mit Mapping-Schlüssel -> Wert-Beziehungen.
KChaloux
2
Zu guter Letzt, wenn Sie wissen, wonach Sie suchen, ist die Hash-Tabelle um die O (1) -Zeit, während das Array im besten Fall O (logN) (sortiert und ohne Duplikate) und O (N) in ist der schlimmste Fall.
JensG
1
+1. Niemand sonst scheint den Punkt angesprochen zu haben, dass Listen semantisch geordnet und Dikte semantisch nachgeschlagen werden, was meiner Meinung nach absolut grundlegend ist.
Benjamin Hodgson
15

Semantisch sind a Dictionary<int, T>und List<T>sehr ähnlich, beide sind Container mit wahlfreiem Zugriff des .NET-Frameworks. Um eine Liste als Ersatz für ein Wörterbuch zu verwenden, benötigen Sie einen speziellen Wert in Ihrem Typ T(wie null), um die leeren Slots in Ihrer Liste darzustellen. Wenn Tes sich nicht um einen nullwertfähigen Typ handelt int, können Sie int?stattdessen einen verwenden. Wenn Sie nur positive Werte speichern möchten, können Sie auch einen speziellen Wert wie -1 verwenden, um leere Slots darzustellen.

Welches Sie auswählen, hängt vom Bereich der Schlüsselwerte ab. Wenn sich Ihre Schlüssel in Dictionary<int, T>in einem ganzzahligen Intervall ohne große Lücken zwischen ihnen befinden (z. B. 80 Werte von [0, ... 100]), ist a List<T>geeigneter, da der Zugriff per Index schneller ist, und In diesem Fall ist der Speicher- und Zeitaufwand im Vergleich zu einem Wörterbuch geringer.

Wenn Ihre Schlüsselwerte 100 intWerte aus einem Bereich wie [0, ..., 1000000] sind, List<T>benötigt a Speicher für 1000000 Werte von T, wobei Ihr Wörterbuch nur Speicher in einer Größenordnung von etwa 100 Werten von T benötigt. 100 Werte von int (plus etwas Overhead, in Wirklichkeit wird etwa das Zweifache des Speichers zum Speichern dieser 100 Schlüssel und Werte erwartet). Im letzteren Fall ist ein Wörterbuch besser geeignet.

Doc Brown
quelle
6
Dies ist der wichtige Unterschied, imho, Dictionary <int, int> kann spärlich sein
jk.
In diesem Fall können wir List <KeyValuePair <int, int >> nicht verwenden? Welches wäre besser für lineare Traversen?
Deepak Mishra
@DeepakMishra: Der Hauptunterschied besteht darin, List<KeyValuePair<int,T>>dass keine O (1) -Nachschlagoperation verfügbar ist. Zweitens können Elemente in List<KeyValuePair<int,T>>einer bestimmten Reihenfolge angeordnet sein, unabhängig von ihren Schlüsselwerten. Wenn Sie Letzteres brauchen, aber nicht Ersteres, List<KeyValuePair<int,T>>oder List<Tuple<int,T>>die bessere Wahl sein könnten. Wenn Sie beides brauchen, gibt es auch OrderedDictionary.
Doc Brown
@DocBrown Welches ist besser für lineare Traversal- (dh Foreach-) und Einfügeoperationen geeignet, da keine direkte Suche erforderlich ist?
Deepak Mishra
@DeepakMishra: Es gibt kein "allgemein besseres" in der Softwareentwicklung. Besser hier könnte bedeuten, schneller, besser zu lesen, weniger Code zu tippen, einfacher für anstehende Anforderungen zu erweitern. Aber im Allgemeinen hören Sie auf, darüber nachzudenken, implementieren Sie eines, das Ihr Problem richtig löst und das für Ihre Augen am einfachsten ist , prüfen Sie, ob es schnell genug für Ihren Zweck ist , und investieren Sie nur mehr Gedanken in es, wenn Sie Nachteile bemerken.
Doc Brown
6

Wie kann man sie als gleichwertig betrachten?

Das Wörterbuch ist spärlich und erlaubt zufällige Einfügungen, macht aber das Durchlaufen in der Reihenfolge zu einem Problem. Die Liste ist nicht spärlich und das Einfügen in der falschen Reihenfolge ist teuer. Sie bietet von Natur aus das Durchlaufen in der Reihenfolge.

Es würde sehr wenige Situationen geben, in denen einer dem anderen nicht dramatisch überlegen war.

Loren Pechtel
quelle
2

Nebenbei: Andere Programmiersprachen bezeichnen diese Art von Datenstruktur als Map und nicht als Dictionary.

Wenn Ihre Daten sinnvoll als Schlüssel / Wert-Paare definiert werden können, bietet ein Wörterbuch einen viel schnelleren Zugriff, wenn Sie einen Wert anhand seines Schlüssels suchen müssen.

Angenommen, Sie haben eine Liste mit Kunden. Jeder Kunde enthält Details wie Name und Adresse sowie eine eindeutige Kundennummer. Angenommen, Sie haben auch eine Liste der Bestellungen, die gerade bearbeitet werden. Jede Bestellung enthält Details zu den Vorgängen und muss die Kundennummer der Person enthalten, die sie bestellt hat.

Wenn eine Bestellung versandbereit ist, müssen Sie die Adresse finden, an die sie gesendet werden soll. Wenn die Kunden als einfache Liste gespeichert sind, müssen Sie die gesamte Liste durchsuchen, um den Kunden mit der richtigen Kundennummer zu finden. Stattdessen können Sie die Kunden in einem Wörterbuch mit der Kundennummer als Schlüssel speichern. Mit dem Wörterbuch können Sie nun in einem Schritt den richtigen Kunden ermitteln, ohne dass eine Suche erforderlich ist.

Simon B
quelle
1

Das Dictionary verwendet Hashing, um nach Daten zu suchen. Ein Dictionary berechnete zuerst einen Hash-Wert für den Schlüssel und dieser Hash-Wert führt zum Zieldaten-Bucket. Danach muss jedes Element im Bucket auf Gleichheit überprüft werden. Tatsächlich ist die Liste jedoch schneller als das Wörterbuch bei der Suche nach dem ersten Element, da im ersten Schritt nichts gesucht werden muss. Im zweiten Schritt muss die Liste jedoch erst das erste Element und dann das zweite Element durchsehen. Daher nimmt die Suche von Schritt zu Schritt mehr Zeit in Anspruch. Je größer die Liste, desto länger dauert es.

Mehr über ... Dictionary Vs List mit Beispiel.

Walshregal
quelle
-1

Wenn der betreffende Code zwei Sätze von korrelierten Werten speichert, bietet die Dictionary-Klasse eine indizierte Methode zum Nachschlagen von Werten mit einem Schlüssel. Wenn es nur einen Satz von Werten gibt, auf diesen Satz jedoch nach dem Zufallsprinzip zugegriffen werden muss (um möglicherweise zu überprüfen, ob ein Schlüssel in einem Satz vorhanden ist) und die Werte eindeutig sind, ist ein HashSet möglicherweise die beste zu verwendende Satzklasse.

JoshL
quelle
-3

Dies sind großartige Antworten, die die Grundlagen zu decken scheinen.

Eine weitere Überlegung, die ich anbieten werde, ist, dass Wörterbücher (in C #) aus Codierungssicht komplexer sind. Wenn sich Listen und Wörterbücher in derselben Codebasis befinden, ist die Pflege des Codes schwieriger, da beide Methoden geringfügige Unterschiede in der Ausführung grundlegender Vorgänge wie Suchen und Sammeln von Objektdaten aufweisen. Ich gehe davon aus, dass Sie eine Liste verwenden sollten, es sei denn, Sie benötigen aus einem berechtigten Grund ein Wörterbuch.

StephenR
quelle
8
Ich stimme dir nicht zu. Dictionary / Map ist eine grundlegende Datenstruktur, mit der jeder Softwareentwickler vertraut sein sollte. So oder so: Sie benötigen einen berechtigten Grund, um eine Datenstruktur zu verwenden. einschließlich Liste.
Steven Evers