Sortieren eines Wörterbuchs in Bezug auf Schlüssel

72

Ich habe ein Wörterbuch in C # wie

Dictionary<Person, int>

und ich möchte dieses Wörterbuch in Bezug auf Schlüssel sortieren (ein Feld in der Klasse Person). Wie kann ich es tun? Jede im Internet verfügbare Hilfe ist die von Listen ohne spezielles Beispiel für die Sortierung des Wörterbuchs. Jede Hilfe wäre sehr dankbar!

SoulReaver
quelle
Ich bin mir nicht sicher, ob ich Ihre Frage verstehe, da ein Wörterbuch nicht in beliebiger Reihenfolge aufgeführt ist. Sie durchlaufen entweder die Schlüssel oder die Werte, die Sie im Handumdrehen leicht sortieren können ...
Rowland Shaw
Dies kann unmöglich das sein, was Sie tatsächlich wollen. Arrays können an Ort und Stelle sortiert werden, da das Ergebnis des Sortierens eines Arrays ein Array ist. Ein Wörterbuch ist jedoch kein Array und kann daher nicht durch das Ergebnis der Sortierung seiner Einträge ersetzt werden. Sortieren Sie die Einträge und speichern Sie das Ergebnis in einem Array oder einer Liste. Und die akzeptierte Antwort ist wahrscheinlich nicht das, was Sie wollen ... Das Eingeben und Zugreifen auf Einträge aus einer SortedList oder einem SortedDictionary ist viel langsamer als aus einem Dictionary.
Jim Balter

Antworten:

146

Sie können a nicht sortieren Dictionary<TKey, TValue>- es ist von Natur aus ungeordnet. (Oder besser gesagt, die Reihenfolge, in der Einträge abgerufen werden, ist implementierungsspezifisch. Sie sollten sich nicht darauf verlassen, dass es zwischen den Versionen auf die gleiche Weise funktioniert, da die Reihenfolge nicht Teil der entworfenen Funktionalität ist.)

Sie können verwenden SortedList<TKey, TValue>oder SortedDictionary<TKey, TValue>beide nach Schlüssel sortieren (auf konfigurierbare Weise, wenn Sie eine IEqualityComparer<T>an den Konstruktor übergeben) - könnten diese für Sie von Nutzen sein?

Achten Sie wenig auf das Wort "Liste" im Namen SortedList- es ist immer noch ein Wörterbuch, da es Schlüssel Werten zuordnet. Es wird mithilfe einer Liste intern und effektiv implementiert. Anstatt nach Hash-Code zu suchen, wird eine binäre Suche durchgeführt. SortedDictionarybasiert ebenfalls auf binären Suchen, jedoch über einen Baum anstelle einer Liste.

Jon Skeet
quelle
2
Seien Sie jedoch vorsichtig bei der Verwendung SortedList<K,V>: Es wird sehr langsam sein, wenn Sie eine große Liste erstellen (vorausgesetzt, die Elemente sind nicht vorsortiert). Normalerweise sollten Sie SortedDictionary<K,V>stattdessen oder einen Drittanbieter verwenden BDictionary<K,V>, um eine ähnliche Leistung zu erzielen, SortedDictionaryohne die Möglichkeit zu verlieren, über den Index oder "nächstgelegenen Schlüssel suchen" auf Elemente zuzugreifen.
Qwertie
Was ist der Vorteil von binären Suchen, anstatt einen Hash neben sortierten Schlüsseln zu verwalten? Warum kümmert es mich, dass die Elemente geordnet sind, wenn ich nicht fast nur geordnete Aufzählungen mache ? Wenn ich mich mehr für die Suche nach einzelnen Elementen interessiere, aber zweitens anhand der Schlüsselreihenfolge aufzählen möchte, kann ich dann keine separate Liste der Schlüssel nach der Antwort von Steve verwalten ? Wenn das meine gewünschte Verwendung ist SortedListund SortedDictionarytatsächlich die falschen Werkzeuge sind, richtig? Das heißt, was ist, wenn ich buchstäblich zu sortieren nur die Wörterbuch will Schlüssel vorhanden?
Ruffin
1
@ Ruffin: Der Vorteil ist die Vermeidung von Komplexität. Ja, soweit mir bekannt ist, gibt es keine integrierte "sortierte und gehashte" Sammlung. Beachten Sie, dass eine solche Sammlung schwieriger zu verwenden und zu erstellen ist - sie muss sowohl eine Gleichheitsvergleichs- und Hashcode-Funktion als auch eine Ordnungsfunktion bereitstellen. Die Aufbewahrung beider Sammlungen ist natürlich auch mit Speicherkosten verbunden. Sie müssten die Kosten für binäre Suchvorgänge im Vergleich zu Hash-Suchvorgängen für Ihre tatsächlichen Daten messen. Möglicherweise stellen Sie fest, dass dies nur dann von Bedeutung ist, wenn Ihre Sammlungen umfangreich sind.
Jon Skeet
@ruffin "Was ist der Vorteil von binären Suchen, anstatt einen Hash neben sortierten Schlüsseln zu verwalten?" - Speicher für die Hash-Tabelle und die Zeit, um sie beim Hinzufügen oder Löschen von Einträgen zu pflegen. "Warum kümmert es mich, dass die Elemente geordnet sind" - wenn es Ihnen egal ist, dass die Elemente geordnet sind, verwenden Sie einfach ein Wörterbuch (das ich im Allgemeinen über SortedList oder SortedDictionary empfehlen würde) ", möchten aber sekundär basierend auf der Schlüsselreihenfolge aufzählen "- Es ist trivial, die aufgezählten KeyValuePairs zu sortieren, wenn Sie sie gelegentlich benötigen: dict.OrderBy (kv => kv.Key)
Jim Balter
1
@ruffin "Was ist, wenn ich buchstäblich nur die vorhandenen Wörterbuchschlüssel sortieren möchte?" - so etwas gibt es nicht - es ist ein Kategoriefehler. Arrays können an Ort und Stelle sortiert werden ... nichts, was kein Array ist, kann es sein. (Nun, mit Ausnahme einer verknüpften Liste mit veränderlichen Knoten, aber das Sortieren an Ort und Stelle wäre verrückt und sehr teuer.) Aber natürlich können Sie so etwas tunvar array = dict.Keys.ToArray(); array.Sort();
Jim Balter
24

Versuchen Sie es mit SortedDictionary

Chris O.
quelle
3
Sie waren nur 21 Sekunden langsamer als Gott, als Sie antworteten. Das ist nicht so schlimm
RBT
12

Die richtige Antwort ist bereits angegeben (verwenden Sie einfach SortedDictionary).

Wenn Sie jedoch zufällig Ihre Sammlung als Wörterbuch behalten müssen, können Sie auf geordnete Weise auf die Wörterbuchschlüssel zugreifen, indem Sie beispielsweise die Schlüssel in einer Liste bestellen und dann über diese Liste auf das Wörterbuch zugreifen. Ein Beispiel...

Dictionary<string, int> dupcheck = new Dictionary<string, int>();

... ein Code, der "dupcheck" ausfüllt, dann ...

if (dupcheck.Count > 0) {
  Console.WriteLine("\ndupcheck (count: {0})\n----", dupcheck.Count);
  var keys_sorted = dupcheck.Keys.ToList();
    keys_sorted.Sort();
  foreach (var k in keys_sorted) {
    Console.WriteLine("{0} = {1}", k, dupcheck[k]);
  }
}

Vergiss das nicht using System.Linq;.

Steve Greene
quelle
"Wenn Sie Ihre Sammlung zufällig als Wörterbuch behalten müssen" - der offensichtliche Grund dafür ist, dass sie viel schneller eingefügt, gelöscht und nachgeschlagen werden kann. Was var keys_sorted = dupcheck.Keys.ToList(); keys_sorted.Sort();- einfacher ist keys_sorted = dupcheck.Keys.OrderBy(k => k).ToList();... und wenn Sie die Werte verwenden wollen, dann nurforeach (var ent in dupcheck.OrderBy(kv => kv.Key)) Console.WriteLine($"{ent.Key} = {ent.Value}");
Jim Balter
Dies ist keine Sortierung eines Dictionary-Objekts, dies ist nur eine Sortierung einer Anzeige und eine Problemumgehung :(
Ambuj
7

Wörterbücher sind von Natur aus nicht sortierbar. Wenn Sie diese Funktion in einem Wörterbuch benötigen, schauen Sie sich stattdessen SortedDictionary an.

Scott Dorman
quelle
4

Schauen Sie sich an SortedDictionary, es gibt sogar eine Konstruktorüberladung, sodass Sie Ihr eigenes IComparable für die Vergleiche übergeben können.

Dave D.
quelle
3

Während Dictionary als Hash-Tabelle implementiert ist, ist SortedDictionary als Rot-Schwarz-Baum implementiert.

Wenn Sie die Reihenfolge in Ihrem Algorithmus nicht nutzen und die Daten nur vor der Ausgabe sortieren müssen , wirkt sich die Verwendung von SortedDictionary negativ auf die Leistung aus .

Sie können das Wörterbuch folgendermaßen "sortieren":

Dictionary<string, int> dictionary = new Dictionary<string, int>();
// algorithm
return new SortedDictionary<string, int>(dictionary);
Draex_
quelle
Wenn Sie die Einträge nach Schlüssel sortieren möchten, verwenden Sie einfachdictionary.OrderBy(kv => kv.Key)
Jim Balter
2

Aufgrund dieser hohen Suchposition fand ich, dass die LINQ OrderBy- Lösung es wert ist, gezeigt zu werden:

class Person
{
    public Person(string firstname, string lastname)
    {
        FirstName = firstname;
        LastName = lastname;
    }
    public string FirstName { get; set; }
    public string LastName { get; set; }
}

static void Main(string[] args)
{
    Dictionary<Person, int> People = new Dictionary<Person, int>();

    People.Add(new Person("John", "Doe"), 1);
    People.Add(new Person("Mary", "Poe"), 2);
    People.Add(new Person("Richard", "Roe"), 3);
    People.Add(new Person("Anne", "Roe"), 4);
    People.Add(new Person("Mark", "Moe"), 5);
    People.Add(new Person("Larry", "Loe"), 6);
    People.Add(new Person("Jane", "Doe"), 7);

    foreach (KeyValuePair<Person, int> person in People.OrderBy(i => i.Key.LastName))
    {
        Debug.WriteLine(person.Key.LastName + ", " + person.Key.FirstName + " - Id: " + person.Value.ToString());
    }
}

Ausgabe:

Doe, John - Id: 1
Doe, Jane - Id: 7
Loe, Larry - Id: 6
Moe, Mark - Id: 5
Poe, Mary - Id: 2
Roe, Richard - Id: 3
Roe, Anne - Id: 4

In diesem Beispiel wäre es sinnvoll, ThenBy auch für Vornamen zu verwenden:

foreach (KeyValuePair<Person, int> person in People.OrderBy(i => i.Key.LastName).ThenBy(i => i.Key.FirstName))

Dann ist die Ausgabe:

Doe, Jane - Id: 7
Doe, John - Id: 1
Loe, Larry - Id: 6
Moe, Mark - Id: 5
Poe, Mary - Id: 2
Roe, Anne - Id: 4
Roe, Richard - Id: 3

LINQ hat auch OrderByDescending und ThenByDescending für diejenigen, die es benötigen.

Daniel S. Fowler
quelle