Keine wirkliche Frage, weil ich die Antwort schon herausgefunden habe, aber immer noch interessant.
Ich dachte immer, dass Hashtabelle der schnellste assoziative Container ist, wenn Sie richtig hashen.
Der folgende Code ist jedoch schrecklich langsam. Es führt nur etwa 1 Million Iterationen aus und benötigt mehr als 2 Minuten für eine Core 2-CPU.
Der Code führt Folgendes aus: Er verwaltet die Sammlung todo der Elemente, die verarbeitet werden müssen. Bei jeder Iteration nimmt es ein Element aus dieser Sammlung (egal welches Element), löscht es, verarbeitet es, wenn es nicht verarbeitet wurde (möglicherweise fügt es weitere Elemente hinzu) und wiederholt dies, bis keine Elemente mehr zu verarbeiten sind.
Der Schuldige scheint die Dictionary.Keys.First () Operation zu sein.
Die Frage ist, warum ist es langsam?
%Vor%Dies führt zu:
%Vor%Einfach Dictionary zu SortedDictionary ändern:
%Vor%300-mal schneller und dabei nur 2-mal weniger Iterationen.
Dasselbe passiert in Java.
Verwendet HashMap anstelle von Dictionary und keySet().iterator().next() anstelle von Keys.First() .
Dictionary<TKey, TValue> unterhält eine Hash-Tabelle.
Der Enumerator durchläuft die Buckets in der Hash-Tabelle, bis er einen nicht leeren Bucket findet, und gibt dann den Wert in diesem Bucket zurück.
Sobald das Wörterbuch groß wird, wird dieser Vorgang teuer
Außerdem wird beim Entfernen eines Elements aus dem Wörterbuch das Buckets-Array nicht verkleinert, sodass der Aufruf First() beim Entfernen von Elementen langsamer wird. (Weil es weiter loopen muss, um einen nicht leeren Bucket zu finden)
Daher wird wiederholt First() aufgerufen und das Entfernen ist O (n 2 ).
Übrigens können Sie die Wertsuche so vermeiden: (Dadurch wird es nicht merklich schneller)
%Vor%Das Wörterbuch macht keine Mühe, eine Liste der Schlüssel zu verwalten. Der Iterator muss also die Eimer laufen. Viele dieser Eimer, besonders für ein großes Wörterbuch, haben viele nichts in ihnen.
Es kann hilfreich sein, OpenJDKs HashIterator.nextEntry und PrivateEntryIterator.nextEntry (die TreeMap.successor verwendet). In der Hash-Version wird eine unbekannte Anzahl von Einträgen gesucht, die nach einem Objekt suchen, das nicht null ist. Dies könnte besonders langsam sein, wenn in der Hash-Tabelle viele Elemente entfernt wurden (was in Ihrem Fall der Fall ist). In TreeMap ist das einzige Laufen, das wir machen, unsere In-Order-Traversierung. Es gibt keine Nullen im Weg (nur an den Blättern).
Nun, Hashtabellen sind nicht sortiert, ich rate, dass sie irgendeine Art von Sortierung durchführen müssen, bevor sie eine Iteration durchführen kann, oder irgendeine Art von Scan, wenn sie bereits sortiert ist, kann sie einfach durchlaufen werden.
Reflector zeigt, dass Dictionary<TKey, TValue> ein Entry<TKey, TValue> -Array enthält, das KeyCollection<TKey, TValue>.Enumerator<TKey, TValue> verwendet. Normalerweise sollte das Nachschlagen relativ schnell sein, da es nur in das Array indizieren kann (vorausgesetzt, Sie möchten kein sortiertes First ):
Jedoch , wenn Sie die ersten Elemente dieses Arrays entfernen, gehen Sie am Ende das Array durch, bis Sie ein nicht leeres finden:
%Vor% Wenn Sie Ihre Einträge entfernen, erhalten Sie mehr und mehr Leerstellen am Anfang des Arrays entries , und es wird langsamer, First das nächste Mal abzurufen.
Ohne zu betrachten, ist die einfachste Implementierung eines sortierten Dictionary eine sortierte Liste (wie TreeSet) von Schlüsseln und einem kombinierten Hash; Die Liste gibt Ihnen die Reihenfolge, das Wörterbuch gibt Ihnen Werte. Somit sind die Schlüssel bereits verfügbar. Hashtable hat keine Schlüssel zur Verfügung, so der Schuldige ist nicht first , es ist keys (alle ohne jeden Beweis, fühlen Sie sich frei, die Hypothese zu testen; D)
Tags und Links algorithm .net performance hashtable