Un reemplazo más rápido para el Diccionario <TKey, TValue>

Question

Necesito un reemplazo rápido para el System.Collections.Generic.Dictionary<TKey, TValue>. Mi aplicación debe ser realmente rápido. Por lo tanto, la sustitución debe apoyar:

• Genéricos
• Añadir
• Get
• Contiene

... y eso es todo. No necesito ningún soporte en LINQ ni nada. Y debe ser rápido.

Un código simple como:

Stopwatch stopWatch = Stopwatch.StartNew(); 

Dictionary<string, string> dictionary = new Dictionary<string, string>(); 
dictionary.Add("fieldName", "fieldValue"); 
dictionary.Add("Title", "fieldVaaaaaaaaaaaaaaaaalue"); 

Console.WriteLine(stopWatch.Elapsed); 

... impresiones 00: 00: 00,0001274, que es mucho de tiempo para mí, ya que mi solicitud está haciendo muchas otras cosas, algunos de ellos de edad bibliotecas lentas que debo usar y que no dependen de mí.

¿Alguna idea sobre cómo implementar una más rápida?

Gracias.

Answer 1

Lo más probable es que esté viendo la compilación de JIT. En mi caja, veo:

00:00:00.0000360 
00:00:00.0000060 

al ejecutarlo dos veces en rápida sucesión dentro del mismo proceso - y no en el depurador. (Asegúrese de no ejecutarlo en el depurador, o es una prueba inútil.)

Ahora, medir cualquier momento que minúsculo es generalmente una mala idea. Tendría que iterar millones de veces para tener una mejor idea de cuánto tiempo está tomando.

¿Tiene buenas razones para creer que es en realidad ralentizando su código, o está basando todo en el tiempo original?

Dudo que encuentre nada significativamente más rápido que Dictionary<TKey, TValue> y me sorprendería mucho descubrir que es el cuello de botella.

EDIT: Acabo de comparar agregar un millón de elementos a un Dictionary<TKey, TValue> donde todas las claves eran objetos existentes (cadenas en una matriz), reutilizando el mismo valor (ya que es irrelevante) y especificando una capacidad de un millón en la construcción - y tomó aproximadamente 0.15s en mi computadora portátil de dos años.

¿Es probable que sea un cuello de botella para usted, dado que ya ha dicho que está utilizando algunas "viejas bibliotecas lentas" en otra parte de su aplicación? Tenga en cuenta que cuanto más lentas sean esas otras bibliotecas, menor será el impacto que tendrá una clase de colección mejorada. Si los cambios del diccionario solo representan el 1% del tiempo total de la aplicación, incluso si pudiéramos proporcionar un diccionario instantáneo, solo aceleraría su aplicación en un 1%.

Como siempre, obtenga un generador de perfiles que le dará una mejor idea de hacia dónde va su tiempo.

Answer 2

Estoy de acuerdo con la suposición de Jon Skeet de que es muy probable que se trate de la compilación de JIT.

Dicho esto, yo quería añadir alguna otra información aquí:

La mayor parte de los problemas de velocidad relacionados con el uso de Dictionary<T,U> no están relacionados con la aplicación de diccionario. Dictionary<T,U> es MUY rápido, listo para usar. Sería difícil superarlo.

Los problemas de velocidad relacionados con las instancias de diccionario casi siempre son realmente problemas de implementación del código hash. Si tiene problemas de velocidad al usar Dictionary<MyCustomClass,MyValue>, revise la implementación GetHashCode() que ha definido en MyCustomClass. Esto es aún más crítico si está utilizando una estructura personalizada como su clave.

Con el fin de obtener un buen rendimiento de diccionario, GetHashCode() debería ser:

1. rápido
2. Capaz de proporcionar códigos hash que generan pocos conflictos. Las instancias únicas deben, cuando sea posible, generar valores hash únicos.

Si lo haces bien, creo que estarás muy satisfecho con la implementación predeterminada del diccionario.

Answer 3

Si realmente necesita un mejor rendimiento, tendrá que renunciar a algo importante, como genéricos, asignación de memoria dinámica, etc. Todas estas características sacrifican algo de rendimiento.

evitaría usando contiene, si es posible, y miran TryGetValue etc.

Answer 4

más probable es que no van a encontrar nada mucho más rápido que diccionario. Yo solo usaría Dictionary. Luego, cuando vea que no está cumpliendo sus objetivos de desempeño, y un generador de perfiles indica que agregar/eliminar del Diccionario son sus obstáculos que puede considerar reemplazar con una clase más específica.

Tenga en cuenta que las funciones como LINQ debido no incurren en ninguna pérdida de rendimiento si no las usa.

Answer 5

No olvide, también está cronometrando el constructor del diccionario en ese código. Hice una prueba, moviendo la llamada al constructor fuera de la medición y bucle 10 veces. Aquí está mi código de prueba:

for (int i = 0; i < 10; i++) 
{ 
    Dictionary<string, string> test = new Dictionary<string, string>(); 

    System.Diagnostics.Stopwatch watch = System.Diagnostics.Stopwatch.StartNew(); 

    test.Add("fieldName", "fieldValue"); 
    test.Add("Title", "fieldavlkajlkdjflkjalkjslkdjfiajwelkrjelrkjavoijl"); 

    Console.WriteLine(watch.Elapsed); 
} 

Console.ReadKey(); 

A continuación se presentan los resultados:

00:00:00.0000607 
00:00:00.0000025 
00:00:00.0000015 
00:00:00.0000015 
00:00:00.0000016 
00:00:00.0000017 
00:00:00.0000016 
00:00:00.0000016 
00:00:00.0000016 
00:00:00.0000015 

No estoy seguro de cuánto más rápido se podría conseguir que eso ...

actualización

Parece que esto refleja los resultados de Jon Skeets también ... JIT.

Answer 6

¿Podría utilizar una lista y definir una enumeración tal que, por ejemplo, fieldName = 0, Title = 1 y usar el índice único de cada propiedad como un índice de búsqueda en la lista? Esa sería la solución más rápida, aunque la menos flexible, ya que estaría vinculado a una enumeración.

Answer 7

¿Cuántos artículos planeas agregar al diccionario?Si bien Dictionary/Hashtable suele ser el más rápido, dependiendo de lo que esté haciendo, puede haber algo más rápido (también mejor adaptado) que un Hashtable (la estructura subyacente en un diccionario). Según el uso, es posible que SortedList sea más rápido si se combina con algún tipo de lista de saltos o incluso un árbol o intentos de autoequilibrado. Especialmente si desea devolver un rango de valores en lugar de un solo valor.

una tabla hash es un buen ajuste cuando:

1. Usted sabe cuántos artículos tiene la intención de almacenar antes de la población de la tabla comienza. ¡El cambio de tamaño dinámico será muy doloroso!
2. usted tiene un buen algoritmo de hash con una distribución uniforme, lo que hace .NET
3. Hay un buen mecanismo para resolución de colisiones, lo que hace .NET
4. Usted está buscando un único valor
5. Puede garantizar que todos los valores serán únicos

Si está realizando alguna compresión, por ejemplo, un RB-Tree es mejor que un Hashtable.

Fuente: http://en.wikipedia.org/wiki/Hashtable#Dynamic_resizing