Warum ist Dictionary.First() so langsam?

Question

Keine wirkliche Frage, weil ich schon die Antwort gefunden habe, aber immer noch interessant.

Ich dachte immer, dass die Hash-Tabelle der schnellste assoziative Container ist, wenn Sie richtig hashen.

Jedoch ist der folgende Code schrecklich langsam. Es führt nur etwa 1 Million Iterationen aus und benötigt für eine Core 2-CPU mehr als 2 Minuten Zeit.

Der Code führt Folgendes aus: Er verwaltet die Sammlung todo der Elemente, die verarbeitet werden müssen. Bei jeder Iteration es ein Element aus dieser Sammlung kommt (egal, welche Artikel), löscht sie, verarbeitet sie, wenn sie nicht verarbeitet wurde (möglicherweise mehr Elemente hinzufügen zu verarbeiten), und wiederholt dies, bis es keine Elemente zu verarbeiten ist.

Der Täter scheint die Dictionary.Keys.First() Betrieb zu sein.

ist die Frage, warum verlangsamen wird?

Stopwatch watch = new Stopwatch(); 
watch.Start(); 

HashSet<int> processed = new HashSet<int>(); 
Dictionary<int, int> todo = new Dictionary<int, int>(); 

todo.Add(1, 1); 
int iterations = 0; 

int limit = 500000; 
while (todo.Count > 0) 
{ 
    iterations++; 
    var key = todo.Keys.First(); 
    var value = todo[key]; 
    todo.Remove(key); 
    if (!processed.Contains(key)) 
    { 
     processed.Add(key); 
     // process item here 
     if (key < limit) { todo[key + 13] = value + 1; todo[key + 7] = value + 1; } 
     // doesn't matter much how 
    } 
} 
Console.WriteLine("Iterations: {0}; Time: {1}.", iterations, watch.Elapsed); 

Daraus ergibt sich:

Iterations: 923007; Time: 00:02:09.8414388. 

Durch einfaches Ändern Wörterbuch zu SortedDictionary ergibt:

Iterations: 499976; Time: 00:00:00.4451514. 

300-mal schneller, während nur 2-mal weniger Iterationen mit.

Das gleiche geschieht in Java. Verwendet HashMap anstelle von Dictionary und keySet().iterator().next() anstelle von Keys.First().

Answer 1

Dictionary<TKey, TValue> verwaltet eine Hash-Tabelle.

Der Enumerator durchläuft die Buckets in der Hash-Tabelle, bis ein nicht leerer Bucket gefunden wird, und gibt den Wert in diesem Bucket zurück.
Sobald das Wörterbuch groß wird, wird dieser Vorgang teuer.
Darüber hinaus schrumpft das Entfernen eines Elements aus dem Wörterbuch nicht das Buckets-Array, so dass der Aufruf langsamer als Sie Elemente entfernen. (Weil es weiter loopen muss, um einen nicht leeren Bucket zu finden)

Daher wiederholt First() aufrufen und entfernen ist O (n).

---

By the way, können Sie den Wert Lookup wie dies vermeiden: (Das wird es nicht schneller spürbar)

var kvp = todo.First(); 

//Use kvp.Key and kcp.Value 

Answer 2

Wörterbuch macht keine Mühe, den Überblick über eine Liste der Schlüssel zu halten. 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, OpenJDK HashIterator.nextEntry und PrivateEntryIterator.nextEntry (die TreeMap.successor verwendet) zu vergleichen. 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).

Answer 3

Ohne zu suchen, ist die einfachste Implementierung eines sortierten Wörterbuchs 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 nicht über Tasten leicht zugänglich, so dass der Täter nicht first, dann ist es keys (alle ohne Spur eines Beweises, um die Hypothese zu testen, fühlen Sie sich frei, D)

Answer 4

Nun, Hash Tables nicht sortiert ist, meine Vermutung ist, es muss irgendeine Art von Sortierung durchführen, bevor es eine Iteration oder irgendeine Art von Scan durchführen kann, wenn es bereits sortiert ist, kann es einfach durchlaufen werden.

Answer 5

Reflector zeigt, dass Dictionary<TKey, TValue> eine Entry<TKey, TValue> Array behauptet, dass es KeyCollection<TKey, TValue>.Enumerator<TKey, TValue> Anwendungen ist. Normalerweise sollte die Suche relativ schnell sein, wie es dem Array nur Index in kann (vorausgesetzt, Sie keine sortiert First wollen):

// Dictionary<TKey. TValue> 
private Entry<TKey, TValue>[] entries; 

jedoch, wenn Sie die ersten Elemente, dass das Entfernen sind Array, dann beenden Sie das Array zu Fuß, bis Sie eine nicht leere finden ein:

// Dictionary<TKey, TValue>.KeyCollection<TKey, TValue>.Enumerator<TKey, TValue> 
while (this.index < this.dictionary.count) { 
    if (this.dictionary.entries[this.index].hashCode >= 0) { 
     this.currentKey = this.dictionary.entries[this.index].key; 
     this.index++; 
     return true; 
    } 
    this.index++; 
} 

Wie Sie Ihre Einträge entfernen, Sie beginnen immer mehr Leergut an der Vorderseite des entries Array bekommen, und es wird langsamer um das nächste Mal First abzurufen.