valid - example c#

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

Question

Necesito un reemplazo rápido para System.Collections.Generic.Dictionary<TKey, TValue> . Mi aplicación debería ser muy rápida. Por lo tanto, el reemplazo debe apoyar:

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

... y eso es. No necesito ningún soporte en LINQ ni nada. Y debería 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);

... imprime 00: 00: 00.0001274, que es mucho tiempo para mí, porque mi aplicación está haciendo muchas otras cosas, algunas de ellas de bibliotecas lentas antiguas que debo usar y que no dependen de mí.

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

Gracias.

Answer 1

¿Cuántos elementos planeas agregar al diccionario? Aunque Dictionary / Hashtable suele ser el más rápido, dependiendo de lo que esté haciendo, puede haber algo más rápido (también conocido como más adecuado) que un Hashtable (la estructura subyacente en un Diccionario). Según el uso, es posible que SortedList pueda ser más rápida si se combina con algún tipo de lista de omisiones o incluso con un árbol o intentos de auto-equilibrio. Especialmente si desea devolver un rango de valores en lugar de un solo valor.

Un Hashtable es un buen ajuste cuando:

1. Usted sabe cuántos artículos pretende almacenar antes de que comience el llenado de la tabla. ¡El cambio de tamaño dinámico será muy doloroso!
2. Tienes un buen algoritmo hash con distribución uniforme, lo que hace .NET
3. Existe un buen mecanismo para la resolución de colisiones, que hace .NET
4. Estás buscando un solo valor
5. Puedes garantizar que todos los valores serán únicos.

Si estás haciendo algo de compresión, por ejemplo, un RB-Tree es mejor que un Hashtable.

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

Answer 2

¿Podría usar 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 atado a una enumeración.

Answer 3

Estoy de acuerdo con la suposición de Jon Skeet de que esta es la compilación JIT más probable.

Dicho esto, quería agregar otra información aquí:

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

Los problemas de velocidad relacionados con las instancias del diccionario son casi siempre problemas de implementación de código hash. Si tiene problemas de velocidad cuando utiliza Dictionary<MyCustomClass,MyValue> , Dictionary<MyCustomClass,MyValue> visitar 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.

Para obtener un buen rendimiento del diccionario, GetHashCode() debe ser:

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

Si lo hace bien, creo que estará muy contento con la implementación predeterminada del Diccionario.

Answer 4

Las probabilidades son que no vas a encontrar nada mucho más rápido que el diccionario. Sólo usaría el diccionario. Luego, cuando vea que no está cumpliendo con sus objetivos de rendimiento, y un generador de perfiles indica que agregar / eliminar del Diccionario son sus cuellos de botella, puede considerar reemplazarlos con una clase más específica.

Tenga en cuenta que las funciones como LINQ no incurrirán en ninguna pérdida de rendimiento si no las utiliza.

Answer 5

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

00:00:00.0000360
00:00:00.0000060

cuando lo ejecuto dos veces en rápida sucesión dentro del mismo proceso, y no en el depurador. (Asegúrese de que no lo está ejecutando en el depurador, o es una prueba sin sentido).

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

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

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

EDITAR: acabo de 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 construcción - y tomó cerca de 0.15s en mi computadora portátil de dos años.

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

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

Answer 6

No olvides que también estás sincronizando el constructor del Diccionario en ese código. Hice una prueba, moviendo la llamada al constructor fuera de la medición, y lo hice 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 podrías llegar a eso ...

Actualizar

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

Answer 7

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

TryGetValue usar Contains si es posible y vería TryGetValue etc.

Answer 8

UTILICE LAS INTS COMO CLAVES PARA UN RENDIMIENTO MÁXIMO:

Para cualquiera que haya venido de Google, si desea exprimir hasta el último bit de rendimiento de un Diccionario, use Ints como teclas. Aquí hay un punto de referencia en el que se comparan las teclas Int vs String: https://jacksondunstan.com/articles/2527

El autor del artículo incluso menciona que vale la pena convertir las cadenas en caracteres si tiene esa necesidad.

Además, tenga en cuenta que este mismo comportamiento se produce en algunos otros lenguajes como PHP. Las matrices asociativas de php -es en los diccionarios de hecho, y si usas Ints en orden ascendente en PHP7, superan enormemente las claves de cadena.