Wann eine SortedList & lt; TKey, TValue & gt; über ein SortedDictionary & lt; TKey, TValue & gt;

Dies erscheinen mag, um ein Duplikat dieses Fragedie fragt "Was ist der Unterschied zwischen SortedList und SortedDictionary?" Leider sind die Antworten nichts mehr tun, als Zitat in der MSDN-Dokumentation (die eindeutig besagt, dass es performance-und memory-Nutzung Unterschiede zwischen den beiden), aber nicht die Antwort auf die Frage.

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

Den SortedList<TKey, TValue> generic
Klasse ist ein binärer Suchbaum mit
O(log n) abrufen, wobei n die
Anzahl der Elemente in der Wörterbuch.
In diesem ist es ähnlich wie die
SortedDictionary<TKey, TValue> generic
Klasse. Die beiden Klassen haben ähnliche
Objekt-Modelle, und beide haben O(log n)
- Abruf. Wo der zwei Klassen
Sie unterscheiden sich jedoch in der Speichernutzung und der Geschwindigkeit der
einsetzen und entfernen:

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

  • SortedDictionary<TKey, TValue> hat
    schneller einführen und entfernen
    Operationen für unsortierte Daten, O(log n)
    im Gegensatz zu O(n) für
    SortedList<TKey, TValue>.

  • Wenn die Liste gefüllt ist, alle auf einmal
    von sortierten Daten, SortedList<TKey,
    TValue>     ist schneller als
    SortedDictionary<TKey, TValue>.

So, klar würde dies indiziert, dass SortedList<TKey, TValue> ist die bessere Wahl es sei denn, Sie müssen schneller, insert-und remove-Operationen für unsortiert Daten.

Bleibt immer noch die Frage, angesichts der Informationen, über welche praktischen (real-world, business case, etc.) Gründe für die Verwendung einer SortedDictionary<TKey, TValue>? Basierend auf den Leistungsdaten, es würde bedeuten, dass es wirklich keine Notwendigkeit zu haben SortedDictionary<TKey, TValue> überhaupt.

InformationsquelleAutor der Frage Scott Dorman | 2009-09-04

  1. 49

    Ich bin mir nicht sicher, wie genau die MSDN-Dokumentation ist auf SortedList und SortedDictionary. Es scheint zu sagen beide sind umgesetzt in einem binären Suchbaum. Aber wenn die SortedList nutzt einen binären such-Baum, warum wäre es viel langsamer auf Ergänzungen als SortedDictionary?

    Anyway, hier sind einige performance-test-Ergebnisse.

    Jeder test arbeitet auf einer SortedList /SortedDictionary mit 10.000 int32 Tasten. Jeder test wird wiederholt 1.000 mal (Release build, Starten ohne Debuggen).

    Die erste Gruppe von tests, hinzufügen von Schlüssel in der Reihenfolge von 0 bis 9.999. Die zweite Gruppe von tests hinzufügen von zufälligen gemischt-Tasten zwischen 0 bis 9.999 (jede Zahl Hinzugefügt wird genau einmal).

    ***** 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

    Als mit jedem profiling, das wichtigste ist die relative performance, nicht die tatsächlichen zahlen.

    Wie Sie sehen können, auf sortierten Daten der sortierten Liste schneller als die SortedDictionary. Auf unsortierten Daten, die SortedList ist etwas schneller auf Abruf, aber etwa 9-mal langsamer auf hinzufügen.

    Wenn beide sind mit binären Bäumen intern, ist es ziemlich überraschend, dass die Add-operation auf unsortierte Daten ist so viel langsamer für SortedList. Es ist möglich, dass die sortierte Liste kann auch sein, das hinzufügen von Elementen zu einer sortierten linearen Datenstruktur zur gleichen Zeit, die würde es langsam nach unten.

    Doch würde man erwarten, dass die Speichernutzung von SortedList gleich oder größer als die oder zumindest gleich der SortedDictionary. Dies widerspricht aber dem, was in der MSDN-Dokumentation sagt.

    InformationsquelleAutor der Antwort Ash

  2. 31

    Ich weiß nicht, warum MSDN sagt, dass SortedList<TKey, TValue> Verwendung einer binären Struktur für seine Umsetzung, weil wenn man sich code mit einem decompiler wie Reflector Sie erkennen, nicht wahr.

    SortedList<TKey, TValue> ist einfach ein array, das wächst über die Zeit.

    Jedes mal, wenn Sie ein element einzufügen, es zunächst prüfen, ob das array hat genug Kapazität, wenn nicht, ist eine größere array neu erstellt und alte Elemente werden kopiert, in der es (wie List<T>)

    Danach, sucht es woum das element einzufügen, verwenden eine binäre Suche (dies ist möglich, da das array mit Wendeschneidplatten und bereits sortiert ist).

    Zu halten, das array sortiert, es fährt (oder schiebt) alle Elemente befindet sich nach der position des Elements eingefügt werden um eine position (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
.
.

    Erklärt, warum die Leistung von SortedList ist so schlimm, wenn Sie einfügen unsortierte Elemente. Es hat zu re-kopieren Sie einige Elemente, die fast jede einlegen. Der einzige Fall, es hat nicht zu tun ist, wenn das element eingefügt werden am Ende des Arrays.

    SortedDictionary<TKey, TValue> ist anders und verwenden Sie einen binären Baum zum einfügen und abrufen der Elemente. Es hat auch einige Kosten zu legen, da manchmal der Baum muss neu ausbalanciert (aber nicht jede insertion).

    Leistung ist sehr ähnlich, während die Suche nach einem element mit SortedList oder SortedDictionary weil Sie beide verwenden eine binäre Suche.

    Meiner Meinung nach, sollten Sie nie Verwendung SortedList nur ein array Sortieren. Es sei denn, Sie haben sehr wenige Elemente, es wird immer schneller zum einfügen von Werten in eine Liste (oder ein array) und dann rufen Sie Sort() Methode.

    SortedList ist vor allem nützlich, wenn Sie eine Liste der Werte, die bereits sortiert ist (z.B.: aus der Datenbank), können Sie es behalten wollen sortiert und führen einige Operationen, nutzen würden es sortiert ist (z.B.: Contains() Methode der SortedList führt eine binäre Suche anstelle der linearen Suche)

    SortedDictionary bietet die gleichen Vorteile als SortedList aber besser, wenn die Werte zum einfügen sind nicht bereits sortiert sind.

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

    InformationsquelleAutor der Antwort tigrou

  3. 10

    Sind Sie gedacht für zwei unterschiedliche Zwecke?

    Gibt es nicht viel semantische Unterschied dieser beiden sammlungstypen .NET machen. Beide bieten keyed-lookup sowie halten die Einträge in der Reihenfolge der Tasten. In den meisten Fällen werden Sie in Ordnung sein mit Ihnen. Vielleicht das einzige Unterscheidungsmerkmal wäre der indizierten Abruf SortedList erlaubt.

    Aber die Leistung?

    Jedoch gibt es einen performance-Unterschied, den die könnte eine stärkere Faktor zwischen Ihnen zu wählen. Hier ist eine tabellarische Ansicht Ihrer asymptotische 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

    Grob zusammenfassen, wollen Sie eine SortedList<K, V> wenn:

    1. Sie benötigen indiziert look-up.
    2. es ist wünschenswert, weniger Speicher-overhead.
    3. Ihre Eingabedaten bereits sortiert sind (sagen Sie es schon bestellt von db).

    Würden Sie stattdessen möchten lieber eine SortedDictionary<K, V> wenn:

    1. relativen insgesamt performance geht (mit Bezug auf die Skalierung).
    2. Ihre Daten ungeordnet.

    Schreiben von code

    Beide SortedList<K, V> und SortedDictionary<K, V> implementieren IDictionary<K, V>also in Ihrem code können Sie zurück IDictionary<K, V> von der Methode oder declare variable als IDictionary<K, V>. Im Grunde verstecken der Implementierung detail, und code, der gegen die Schnittstelle. 

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

    In Zukunft einfacher an-Schalter aus, wenn Sie nicht zufrieden mit der Leistung Merkmal einer Sammlung.

    Für mehr info auf die beiden Sammlung-Typen finden Sie in der original - Frage verknüpft.

    InformationsquelleAutor der Antwort nawfal

  4. 3

    Visuelle Darstellung der performance-Unterschiede.

    Wann eine SortedList & lt; TKey, TValue & gt; über ein SortedDictionary & lt; TKey, TValue & gt;

    InformationsquelleAutor der Antwort Lev

  5. 2

    Das ist alles dort ist zu ihm. Abruf von Tasten vergleichbar ist, sondern ist darüber hinaus viel schneller mit Wörterbüchern.

    Ich versuche, SortedList, so viel wie möglich, weil es mir erlaubt, zu iterieren über die Schlüssel und Wert-Sammlungen. Dies ist nicht möglich, mit dem SortedDictionary soweit ich weiß.

    Ich bin mir nicht sicher, aber soweit ich weiß, Wörterbücher speichern von Daten in Baumstrukturen, in der Erwägung, dass die Liste speichern von Daten in linearen arrays. Das erklärt, warum das einführen und entfernen sehr viel schneller mit Wörterbüchern, da weniger Speicher verschoben werden. Es erklärt auch, warum Sie iterieren über SortedLists aber nicht SortedDictionary.

    InformationsquelleAutor der Antwort David Rutten

Schreibe einen Kommentar