SortedList <>, SortedDictionary <> und Dictionary <>

98

Ich finde das SortedList<TKey, TValue> SortedDictionary<TKey, TValue>und Dictionary<TKey, TValue>implementiere die gleichen Schnittstellen.

  1. Wann sollten wir uns für SortedListund SortedDictionaryüber entscheiden Dictionary?
  2. Was ist der Unterschied zwischen SortedListund SortedDictionaryin Bezug auf die Anwendung?
Sunder
quelle

Antworten:

101
  1. Wenn Sie über die Elemente in einem der beiden Elemente iterieren, werden die Elemente sortiert. Nicht so bei Dictionary<T,V>.

  2. MSDN behebt den Unterschied zwischen SortedList<T,V>und SortedDictionary<T,V>:

Die generische Klasse SortedDictionary (TKey, TValue) ist ein binärer Suchbaum mit O-Abruf (log n), wobei n die Anzahl der Elemente im Wörterbuch ist. In dieser Hinsicht ähnelt es der generischen Klasse SortedList (TKey, TValue). Die beiden Klassen haben ähnliche Objektmodelle und beide haben einen O (log n) -Abruf. Wo sich die beiden Klassen unterscheiden, ist die Speichernutzung und die Geschwindigkeit des Einfügens und Entfernens:

SortedList (TKey, TValue) benötigt weniger Speicher als SortedDictionary (TKey, TValue).

SortedDictionary (TKey, TValue) bietet schnellere Einfüge- und Entfernungsvorgänge für unsortierte Daten: O (log n) im Gegensatz zu O (n) für SortedList (TKey, TValue).

Wenn die Liste aus sortierten Daten auf einmal gefüllt wird, ist SortedList (TKey, TValue) schneller als SortedDictionary (TKey, TValue).

Szymon Rozga
quelle
21
Ein weiterer praktischer Unterschied besteht darin, dass SortedListSie nach Index abrufen können (im Gegensatz zum Abrufen nach Schlüssel) und SortedDictionarynicht.
Andrew Savinykh
65

Geben Sie hier die Bildbeschreibung ein

Ich würde den Unterschied zwischen Wörterbüchern erwähnen.

Das obige Bild zeigt, dass dies Dictionary<K,V>in jedem Fall gleich oder schneller ist als Sortedanalog, aber wenn die Reihenfolge der Elemente erforderlich ist, z. B. um sie zu drucken,Sorted eines ausgewählt.

Src: http://people.cs.aau.dk/~normark/oop-csharp/html/notes/collections-note-time-complexity-dictionaries.html

Lev
quelle
1
Hervorragende Übersicht. Obwohl dies nicht in der ursprünglichen Frage enthalten ist, sollte beachtet werden, dass, wenn Sie zwischen den ImmutableVersionen dieser Wörterbücher wählen , die SortedVersionen häufig tatsächlich um etwa 40-50% schneller sind als die nicht sortierten Gegenstücke (immer noch O(log(n)), aber merklich schneller pro Operation). . Die Timings können jedoch je nach Sortierung der Eingabe unterschiedlich sein. Siehe stackoverflow.com/a/30638592/111575
Abel
21

Um die Ergebnisse eines Leistungstests - SortedList vs. SortedDictionary vs. Dictionary vs. Hashtable - zusammenzufassen , die Ergebnisse für verschiedene Szenarien vom Besten zum Schlechtesten:

Speichernutzung:

SortedList<T,T>
Hashtable
SortedDictionary<T,T>
Dictionary<T,T>

Einfügungen:

Dictionary<T,T>
Hashtable
SortedDictionary<T,T>
SortedList<T,T>

Suchvorgänge:

Hashtable
Dictionary<T,T>
SortedList<T,T>
SortedDictionary<T,T>

für jede Schleifenoperation

SortedList<T,T>
Dictionary<T,T>
Hashtable
SortedDictionary<T,T>
NullReference
quelle
1
Wenn diese Testergebnisse der Prüfung kann man die Frage stellen raison d'etre von SortedDictionary.
Beawolf
1
Wenn Sie es Collectionbrauchen, können sortedSie vergessen Hashtableund Dictionary: Wenn Sie Ihre Sammlung auf einmal füllen -> wählen Sie SortedList, aber wenn Sie damit rechnen, dass Sie häufig .Addund .RemoveElemente benötigen -> wählen Sie SortedDictionary.
Ama
Möglicherweise muss geklärt werden, was sortedbedeutet: Wenn Sie a For Each MyItem in Collectionausführen, anstatt in der Reihenfolge verarbeitet zu werden, in der Sie .Adddie Elemente ursprünglich bearbeitet haben , sorted Collectionwerden sie in einer Reihenfolge verarbeitet, die den Kriterien für die KeyWerte entspricht (definiert in a IComparer). Wenn Ihre Schlüssel beispielsweise Zeichenfolgen sind, wird Ihre Sammlung standardmäßig in der alphabetischen Reihenfolge Ihrer Schlüssel verarbeitet. Sie können jedoch jederzeit eine benutzerdefinierte Sortierregel definieren.
Ama
9
  1. Wenn Sie möchten, dass die Sammlung nach Schlüssel sortiert wird, wenn Sie darüber iterieren. Wenn Sie Ihre Daten nicht sortieren müssen, sind Sie mit nur einem Wörterbuch besser dran, da es eine bessere Leistung bietet.

  2. SortedList und SortedDictionary machen so ziemlich dasselbe, sind jedoch unterschiedlich implementiert und haben daher unterschiedliche Stärken und Schwächen , die hier erläutert werden .

Meta-Knight
quelle
8

Ich kann sehen, dass sich die vorgeschlagenen Antworten auf die Leistung konzentrieren. Der folgende Artikel enthält keine neuen Informationen zur Leistung, erläutert jedoch die zugrunde liegenden Mechanismen. Beachten Sie auch, dass es sich nicht auf die drei Collectionin der Frage genannten Typen konzentriert, sondern alle Typen des System.Collections.GenericNamespace anspricht .

http://geekswithblogs.net/BlackRabbitCoder/archive/2011/06/16/c.net-fundamentals-choosing-the-right-collection-class.aspx

Auszüge:

Wörterbuch <>

Das Wörterbuch ist wahrscheinlich die am häufigsten verwendete assoziative Containerklasse. Das Wörterbuch ist die schnellste Klasse für assoziative Suchvorgänge / Einfügungen / Löschungen, da es eine Hash-Tabelle unter dem Deckblatt verwendet . Da die Schlüssel gehasht sind, sollte der Schlüsseltyp GetHashCode () und Equals () korrekt implementieren, oder Sie sollten dem Wörterbuch bei der Erstellung einen externen IEqualityComparer bereitstellen. Die Einfüge- / Lösch- / Nachschlagezeit von Elementen im Wörterbuch ist die amortisierte konstante Zeit - O (1) - was bedeutet, dass die Zeit, die benötigt wird, um etwas zu finden, relativ konstant bleibt, egal wie groß das Wörterbuch wird. Dies ist für Hochgeschwindigkeitssuchen sehr wünschenswert. Der einzige Nachteil ist, dass das Wörterbuch aufgrund der Verwendung einer Hash-Tabelle ungeordnet istSie können die Elemente in einem Wörterbuch nicht einfach der Reihe nach durchlaufen .

SortedDictionary <>

Das SortedDictionary ähnelt dem verwendeten Dictionary, unterscheidet sich jedoch in der Implementierung erheblich. Das SortedDictionary verwendet einen Binärbaum unter der Abdeckung, um die Elemente in der Reihenfolge nach dem Schlüssel zu verwalten . Infolge der Sortierung muss der für den Schlüssel verwendete Typ IComparable korrekt implementieren, damit die Schlüssel korrekt sortiert werden können. Das sortierte Wörterbuch tauscht ein wenig Nachschlagzeit gegen die Fähigkeit, die Elemente in der richtigen Reihenfolge zu halten. Daher sind die Einfüge- / Lösch- / Nachschlagezeiten in einem sortierten Wörterbuch logarithmisch - O (log n). Im Allgemeinen können Sie mit logarithmischer Zeit die Größe der Sammlung verdoppeln, und es muss nur ein zusätzlicher Vergleich durchgeführt werden, um den Artikel zu finden. Verwenden Sie das SortedDictionary, wenn Sie schnell nachschlagen möchten, aber auch die Sammlung nach Schlüssel sortieren möchten.

SortedList <>

Die SortedList ist die andere sortierte assoziative Containerklasse in den generischen Containern. Wieder verwendet SortedList wie SortedDictionary einen Schlüssel, um Schlüssel-Wert-Paare zu sortieren . Im Gegensatz zu SortedDictionary werden Elemente in einer SortedList jedoch als sortiertes Array von Elementen gespeichert. Dies bedeutet, dass Einfügungen und Löschungen linear sind - O (n) -, da beim Löschen oder Hinzufügen eines Elements möglicherweise alle Elemente in der Liste nach oben oder unten verschoben werden. Die Suchzeit ist jedoch O (log n), da die SortedList eine binäre Suche verwenden kann, um jedes Element in der Liste anhand seines Schlüssels zu finden. Warum sollten Sie das jemals tun wollen? Die Antwort lautet: Wenn Sie die SortedList im Voraus laden, werden die Einfügungen langsamer. Da die Array-Indizierung jedoch schneller ist als das Folgen von Objektverknüpfungen, sind Suchvorgänge geringfügig schneller als bei einem SortedDictionary. Ich würde dies wieder in Situationen verwenden, in denen Sie schnell nachschlagen und die Sammlung in der Reihenfolge des Schlüssels verwalten möchten und in der Einfügungen und Löschungen selten sind.


Vorläufige Zusammenfassung der zugrunde liegenden Verfahren

Feedback ist sehr willkommen, da ich sicher nicht alles richtig gemacht habe.

  • Alle Arrays sind von Größe n .
  • Nicht sortiertes Array = .Add / .Remove ist O (1), aber .Item (i) ist O (n).
  • Sortiertes Array = .Add / .Remove ist O (n), aber .Item (i) ist O (log n).

Wörterbuch

Erinnerung

KeyArray(n) -> non-sorted array<pointer>
ItemArray(n) -> non-sorted array<pointer>
HashArray(n) -> sorted array<hashvalue>

Hinzufügen

  1. Addiere HashArray(n) = Key.GetHash# O (1)
  2. Addiere KeyArray(n) = PointerToKey# O (1)
  3. Addiere ItemArray(n) = PointerToItem# O (1)

Entfernen

  1. For i = 0 to n, finde iwo HashArray(i) = Key.GetHash # O (log n) (sortiertes Array)
  2. Entfernen Sie HashArray(i)# O (n) (sortiertes Array)
  3. Entfernen Sie KeyArray(i)# O (1)
  4. Entfernen Sie ItemArray(i)# O (1)

Gegenstand erhalten

  1. For i = 0 to n, finde iwo HashArray(i) = Key.GetHash# O (log n) (sortiertes Array)
  2. Rückkehr ItemArray(i)

Durchschleifen

  1. For i = 0 to n, Rückkehr ItemArray(i)

SortedDictionary

Erinnerung

KeyArray(n) = non-sorted array<pointer>
ItemArray(n) = non-sorted array<pointer>
OrderArray(n) = sorted array<pointer>

Hinzufügen

  1. Addiere KeyArray(n) = PointerToKey# O (1)
  2. Addiere ItemArray(n) = PointerToItem# O (1)
  3. For i = 0 to n, finde iwo KeyArray(i-1) < Key < KeyArray(i)(mit ICompare) # O (n)
  4. Addiere OrderArray(i) = n# O (n) (sortiertes Array)

Entfernen

  1. For i = 0 to n, finde iwo KeyArray(i).GetHash = Key.GetHash# O (n)
  2. Entferne KeyArray(SortArray(i))# O (n)
  3. Entferne ItemArray(SortArray(i))# O (n)
  4. Entfernen Sie OrderArray(i)# O (n) (sortiertes Array)

Gegenstand erhalten

  1. For i = 0 to n, finde iwo KeyArray(i).GetHash = Key.GetHash# O (n)
  2. Rückkehr ItemArray(i)

Durchschleifen

  1. For i = 0 to n, Rückkehr ItemArray(OrderArray(i))

SortedList

Erinnerung

KeyArray(n) = sorted array<pointer>
ItemArray(n) = sorted array<pointer>

Hinzufügen

  1. For i = 0 to n, finde iwo KeyArray(i-1) < Key < KeyArray(i)(mit ICompare) # O (log n)
  2. Addiere KeyArray(i) = PointerToKey# O (n)
  3. Addiere ItemArray(i) = PointerToItem# O (n)

Entfernen

  1. For i = 0 to n, finde iwoKeyArray(i).GetHash = Key.GetHash# O (log n)
  2. Entferne KeyArray(i)# O (n)
  3. Entferne ItemArray(i)# O (n)

Gegenstand erhalten

  1. For i = 0 to n, finde iwo KeyArray(i).GetHash = Key.GetHash# O (log n)
  2. Rückkehr ItemArray(i)

Durchschleifen

  1. For i = 0 to n, Rückkehr ItemArray(i)
Ama
quelle
0

Beim Versuch, jedem von @Lev präsentierten Fall eine Leistungsbewertung zuzuweisen, habe ich die folgenden Werte verwendet:

  • O (1) = 3
  • O (log n) = 2
  • O (n) = 1
  • O (1) oder O (n) = 2
  • O (log n) oder O (n) = 1,5

Die Ergebnisse sind (höher = besser):

Dictionary:       12.0 
SortedDictionary:  9.0 
SortedList:        6.5

Natürlich wird jeder Anwendungsfall bestimmten Vorgängen mehr Gewicht verleihen.

Jaime
quelle
1
Als Faustregel gilt, dass das Gewicht von O (log n) log (n) / log (2) (+1 jedes Mal, wenn sich n verdoppelt) beträgt, während das Gewicht von O (n) n beträgt. Ihre Gewichtung wäre also für Größen von bis zu 4 korrekt. Bei allem, was darüber hinausgeht, steigt Ihr Verhältnis von 2: 1 schnell an. Wenn zum Beispiel n = 100 ist, sollten Sie O (log n) = 15 haben. Nach einem ähnlichen Gedanken würde Ihr O (1) 100 wiegen. Schlussfolgerung: O (n) verliert den Kampf ziemlich schnell. Wenn dies nicht der Fall ist, bedeutet dies, dass Ihr Array klein ist und die Effizienz keine Rolle spielt.
Ama