No es una pregunta real porque ya encontré la respuesta, pero aún es algo interesante.¿Por qué Dictionary.First() es tan lento?
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()
.
Los diccionarios están desordenados. – SLaks
Eso no es Java, ¿es ??? – polygenelubricants
@polygenelubricants: está etiquetado como java y .net, y en su última oración OP dice "Lo mismo pasa en Java" – Amadan