Wann sollte eine SortedList <TKey, TValue> über ein SortedDictionary <TKey, TValue> verwendet werden?

Question

Dies scheint ein Duplikat von dieser question, die fragt "Was ist der Unterschied zwischen SortedList und SortedDictionary?" Leider geben die Antworten nichts anderes als die MSDN-Dokumentation an (die eindeutig besagt, dass zwischen beiden Leistungsunterschiede und Unterschiede in der Speicherauslastung bestehen), beantworten die Frage jedoch nicht.

In der Tat (und so diese Frage nicht die gleichen Antworten bekommt), nach MSDN:

Die SortedList<TKey, TValue> generic Klasse ist ein binärer Suchbaum mit O Retrieval (n log), wobei n ist die Anzahl der Elemente im Wörterbuch. In diesem ist es ähnlich der SortedDictionary<TKey, TValue> generischen Klasse. Die beiden Klassen haben ähnliche Objektmodelle, und beide haben O (log n) Abruf. Wo die beiden Klassen in Speicher zu verwenden und die Geschwindigkeit der Einsetzen und Entfernen unterscheiden ist:

• SortedList<TKey, TValue> verwendet weniger Speicher als SortedDictionary<TKey, TValue>.

• SortedDictionary<TKey, TValue> hat schnellere Einsetzen und Entfernen Operationen für unsortierte Daten, O (log n) zu O im Gegensatz (n) für SortedList<TKey, TValue>.

• Wenn die Liste auf einmal bevölkert von sortierten Daten, SortedList<TKey, TValue> ist schneller als SortedDictionary<TKey, TValue>. So

, klar würde dies darauf hin, dass SortedList<TKey, TValue> die bessere Wahl ist, es sei denn Sie müssen schneller einsetzen und Operationen für unsortiert Daten entfernen.

Die Frage bleibt immer noch, angesichts der oben genannten Informationen, was sind die praktischen (Real-World, Business Case, etc.) Gründe für die Verwendung eines SortedDictionary<TKey, TValue>? Basierend auf den Leistungsinformationen würde dies bedeuten, dass es wirklich keinen Bedarf gibt, SortedDictionary<TKey, TValue> überhaupt zu haben.

Answer 1

Das ist alles, was dazu gehört. Das Abrufen von Schlüsseln ist vergleichbar, aber das Hinzufügen von Wörterbüchern ist viel schneller.

Ich versuche, SortedList so viel wie möglich zu verwenden, weil es mir erlaubt, über die Schlüssel und Wertansammlungen zu iterieren. Dies ist mit SortedDictionary meines Wissens nicht möglich.

Ich bin mir nicht sicher, aber soweit ich weiß Wörterbücher speichern Daten in Tree-Strukturen, während List Daten in linearen Arrays speichern. Das erklärt, warum das Einfügen und Entfernen bei Wörterbüchern viel schneller ist, da weniger Speicher verschoben werden muss. Es erklärt auch, warum Sie über SortedLists aber nicht SortedDictionary iterieren können.

Answer 2

Ich bin mir nicht sicher, wie genau die MSDN-Dokumentation auf SortedList und SortedDictionary ist. Es scheint zu sagen, dass beide mit einem binären Suchbaum implementiert sind.Aber wenn die SortedList einen binären Suchbaum verwendet, warum wäre es bei Additionen viel langsamer als SortedDictionary?

Wie auch immer, hier sind einige Leistung Testergebnisse.

Jeder Test wird mit einem SortedList/SortedDictionary ausgeführt, der 10.000 int32-Schlüssel enthält. Jeder Test wird 1.000 Mal wiederholt (Release-Build, Start ohne Debugging).

Die erste Gruppe von Tests fügt Schlüssel in der Reihenfolge von 0 bis 9.999 hinzu. Die zweite Gruppe von Tests fügt zufällig gemischte Schlüssel zwischen 0 und 9.999 hinzu (jede Zahl wird genau einmal addiert).

***** Tests.PerformanceTests.SortedTest 

SortedDictionary Add sorted: 4411 ms 
SortedDictionary Get sorted: 2374 ms 


SortedList Add sorted: 1422 ms 
SortedList Get sorted: 1843 ms 

***** Tests.PerformanceTests.UnsortedTest 

SortedDictionary Add unsorted: 4640 ms 
SortedDictionary Get unsorted: 2903 ms 


SortedList Add unsorted: 36559 ms 
SortedList Get unsorted: 2243 ms 

Wie bei jedem Profiling ist die relative Leistung wichtig, nicht die tatsächlichen Zahlen. Wie Sie sehen können, ist die sortierte Liste schneller als die SortedDictionary. Bei unsortierten Daten ist die SortedList beim Abruf etwas schneller, beim Hinzufügen jedoch etwa 9 mal langsamer.

Wenn beide intern binäre Bäume verwenden, ist es ziemlich überraschend, dass die Operation Hinzufügen bei unsortierten Daten für SortedList so viel langsamer ist. Es ist möglich, dass die sortierte Liste auch Elemente zu einer sortierten linearen Datenstruktur gleichzeitig hinzufügt, was dies verlangsamen würde.

Sie würden jedoch erwarten, dass die Speichernutzung eines SortedList gleich oder größer als oder mindestens gleich SortedDictionary ist. Dies widerspricht jedoch der MSDN-Dokumentation.

Answer 3

Ich weiß nicht, warum MSDN sagt, dass SortedList<TKey, TValue> einen binären Baum für seine Implementierung verwenden, denn wenn Sie Code mit einem Decompiler wie Reflector betrachten, erkennen Sie, dass es nicht wahr ist.

SortedList<TKey, TValue> ist einfach ein Array, das im Laufe der Zeit wächst.

Jedes Mal, wenn Sie ein Element einzufügen, zunächst prüfen, ob das Array genügend Kapazität hat, wenn nicht, ein größeres Array neu erstellt wird und alte Elemente werden kopiert hinein (wie List<T>)

Danach sucht er wo, um das Element mit einer binären Suche einfügen (das ist möglich, da das Array indiziert und bereits sortiert ist).

Um das Array zu halten sortiert, bewegt es sich (oder drückt), um alle Elemente liegt nach Position des Elements um eine Position eingefügt werden (mit Array.Copy()).

ZB:

// we want to insert "3" 

2 
4 <= 3 
5 
8 
9 
.  
.  
. 

// we have to move some elements first 

2 
. <= 3 
4 
5 | 
8 v 
9 
. 
. 

Das erklärt, warum die Leistung von SortedList so schlecht ist, wenn Sie unsortierten Elemente einzufügen. Es muss einige Elemente fast jede Einfügung neu kopieren. Der einzige Fall, den es nicht zu tun braucht, ist, wenn das Element am Ende des Arrays eingefügt werden muss.

SortedDictionary<TKey, TValue> ist anders und verwenden einen Binärbaum zum Einfügen und Abrufen von Elementen. Es hat auch einige Kosten bei der Einfügung, weil manchmal der Baum neu ausbalanciert werden muss (aber nicht jede Einfügung).

Leistung ist sehr ähnlich beim Suchen eines Elements mit SortedList oder SortedDictionary, weil beide eine binäre Suche verwenden.

---

Meiner Meinung nach, sollten Sie nie Gebrauch SortedList nur ein Array sortieren. Sofern Sie nicht über sehr wenige Elemente verfügen, ist es immer schneller, Werte in eine Liste (oder ein Array) einzufügen und dann die Methode Sort() aufzurufen.

SortedList meist nützlich, wenn Sie eine Liste von Werten haben bereits sortiert (zB: aus der Datenbank), die Sie behalten möchten es sortiert und einige Operationen durchführen, die den Vorteil nehmen würde es sortiert wird (zB: Contains() Verfahren von SortedList führt eine binäre Suche anstelle von linearer Suche)

SortedDictionary bietet die gleichen Vorteile wie SortedList, führt aber besser aus, wenn die einzufügenden Werte nicht bereits sortiert sind.

---

EDIT: Wenn Sie .NET Framework 4.5 verwenden, eine Alternative zu SortedDictionary<TKey, TValue> ist SortedSet<T>. Es funktioniert genauso wie SortedDictionary mit einem binären Baum, aber die Schlüssel und Werte sind hier gleich.

Answer 4

Sind sie für zwei verschiedene Zwecke gedacht?

Es gibt nicht viel semantischen Unterschied diese beiden Sammlungstypen in .NET machen. Sie bieten sowohl Schlüsselsuche als auch die Einträge in der Reihenfolge der Schlüssel. In den meisten Fällen werden Sie mit beiden einverstanden sein. Vielleicht wäre das einzige Unterscheidungsmerkmal die indizierte Abfrage SortedList erlaubt.

Aber Leistung?

Allerdings gibt es einen Leistungsunterschied, der könnte ein stärkerer Faktor sein, zwischen ihnen zu wählen. Hier ist eine tabellarische Ansicht ihrer asymptotischen Komplexität.

+------------------+---------+----------+--------+----------+----------+---------+ 
| Collection  | Indexed | Keyed | Value | Addition | Removal | Memory | 
|     | lookup | lookup | lookup |   |   |   | 
+------------------+---------+----------+--------+----------+----------+---------+ 
| SortedList  | O(1) | O(log n) | O(n) | O(n)* | O(n)  | Lesser | 
| SortedDictionary | n/a  | O(log n) | O(n) | O(log n) | O(log n) | Greater | 
+------------------+---------+----------+--------+----------+----------+---------+ 

* Insertion is O(1) for data that are already in sort order, so that each 
    element is added to the end of the list (assuming no resize is required). 

Zusammenfassung

Um grob zusammenzufassen, möchten Sie eine SortedList<K, V> wenn:

1. Sie benötigen Nachschau indiziert.
2. ist es wünschenswert, weniger Speicheraufwand zu haben.
3. Ihre Eingabedaten sind bereits sortiert (sagen Sie, Sie haben es bereits bestellt von db).

Sie würden stattdessen ein SortedDictionary<K, V>, wenn sie es vorziehen wollen:

1. relativen Gesamt Leistungsfragen (in Bezug auf die Skalierung).
2. Ihre Eingabedaten sind ungeordnet.

Code schreiben

Sowohl SortedList<K, V> und SortedDictionary<K, V>IDictionary<K, V> implementieren, so in Ihrem Code Sie IDictionary<K, V> aus dem Verfahren oder erklären Variable als IDictionary<K, V> zurückkehren kann. Verstecken Sie im Grunde das Implementierungsdetail und Code gegen Schnittstelle.

IDictionary<K, V> x = new SortedDictionary<K, V>(); //for eg. 

In Zukunft ist es einfacher, von beiden zu wechseln, falls Sie mit der Leistungsmerkmale einer Kollektion nicht zufrieden sind.

---

Für weitere Informationen über die beiden Sammlungstypen finden Sie in der ursprünglichen question verknüpft.

Answer 5

Visuelle Darstellung von Leistungsunterschieden.