¿Por qué Dictionary.First() es tan lento?

Question

No es una pregunta real porque ya encontré la respuesta, pero aún es algo interesante.

Siempre he pensado que la tabla hash es el contenedor asociativo más rápido si hash correctamente.

Sin embargo, el siguiente código es terriblemente lento. Ejecuta solo alrededor de 1 millón de iteraciones y tarda más de 2 minutos en una CPU Core 2.

El código hace lo siguiente: mantiene la colección todo de los elementos que necesita procesar. En cada iteración toma un elemento de esta colección (no importa qué elemento), lo elimina, lo procesa si no se procesó (posiblemente agregando más elementos para procesar) y lo repite hasta que no haya elementos para procesar.

El culpable parece ser la operación Dictionary.Keys.First().

La pregunta es ¿por qué es lenta?

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); 

Esto se traduce en:

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

Simplemente cambiando diccionario a los rendimientos SortedDictionary:

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

300 veces más rápido, mientras que tiene solamente 2 veces menos iteraciones.

Lo mismo sucede en java. Usado HashMap en lugar de Dictionary y keySet().iterator().next() en lugar de Keys.First().

Answer 1

Dictionary<TKey, TValue> mantiene una tabla hash.

Su enumerador recorrerá las cubetas de la tabla hash hasta que encuentre un depósito no vacío, luego devolverá el valor en ese depósito.
Una vez que el diccionario crece, esta operación se vuelve costosa.
Además, la eliminación de un elemento del diccionario no reduce la matriz de cubos, por lo que la llamada First() obtiene más lenta a medida que elimina los elementos. (Debido a que tiene al bucle más lejos para encontrar un cubo no vacío)

Por lo tanto, llamar repetidamente First() y la eliminación es O (n).

---

Por cierto, se puede evitar la búsqueda de valor como esto: (Esto no hará que sea mucho más rápido)

var kvp = todo.First(); 

//Use kvp.Key and kcp.Value 

Answer 2

Diccionario no hace ningún esfuerzo para realizar un seguimiento de una lista de claves. Entonces el iterador necesita recorrer los cubos. Muchos de estos segmentos, particularmente para un diccionario grande, muchos no tienen nada en ellos.

Puede ser útil comparar OpenJDK HashIterator.nextEntry y PrivateEntryIterator.nextEntry (que usa TreeMap.successor). La versión de hash camina con un número desconocido de entradas buscando una que no sea nula. Esto podría ser particularmente lento si la tabla hash ha tenido muchos elementos eliminados (que tiene en su caso). En TreeMap, la única caminata que hacemos es nuestro recorrido en orden. No hay nulos en el camino (solo en las hojas).

Answer 3

Sin mirar, la implementación más simple de un diccionario ordenado es una lista ordenada (como TreeSet) de claves y un hash combinado; la lista te da el orden, el diccionario te da valores. Por lo tanto, las claves ya están disponibles. Tabla hash no tiene teclas de fácil acceso, por lo que el culpable no es first, es keys (todos, sin ninguna pizca de evidencia, no dude en probar la hipótesis; D)

Answer 4

Bueno, las tablas hash no se ordenan, yo creo que es tiene que hacer algún tipo de ordenamiento antes de que pueda hacer una iteración, o algún tipo de escaneo, si ya está ordenado, puede atravesarlo.

Answer 5

Reflector muestra que Dictionary<TKey, TValue> mantiene una matriz Entry<TKey, TValue> que es KeyCollection<TKey, TValue>.Enumerator<TKey, TValue> usos. Normalmente, la búsqueda debe ser relativamente rápido, ya que puede simplemente índice en la matriz (suponiendo que no quiere una ordenados First):

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

Sin embargo, si quieres eliminar los primeros elementos de esa matriz, entonces se termina caminando la matriz hasta que encuentre una que no esté vacía uno:

// 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++; 
} 

Como se quita las entradas, que comienza a recibir más y más se vacía en la parte delantera de la matriz entries, y se hace más lenta para recuperar First la próxima vez.