objetos - modificar valor diccionario c#

Optimización de búsquedas: búsquedas de clave de diccionario frente a búsquedas de índice de matriz

Question

Estoy escribiendo un evaluador de manos de póker de 7 cartas como uno de mis proyectos favoritos. Al intentar optimizar su velocidad (me gusta el desafío), me sorprendió descubrir que el rendimiento de las búsquedas de claves en el diccionario era bastante lento en comparación con las búsquedas de índices de matriz.

Por ejemplo, ejecuté este código de muestra que enumera todos los 52, elija 7 = 133,784,560 manos de 7 cartas posibles:

var intDict = new Dictionary<int, int>();
var intList = new List<int>();
for (int i = 0; i < 100000; i ++)
{
    intDict.Add(i, i);  
    intList.Add(i);
}

int result;

var sw = new Stopwatch();
sw.Start();
for (int card1 = 0; card1 < 46; card1++)
  for (int card2 = card1 + 1; card2 < 47; card2++)
    for (int card3 = card2 + 1; card3 < 48; card3++)
      for (int card4 = card3 + 1; card4 < 49; card4++)
        for (int card5 = card4 + 1; card5 < 50; card5++)
          for (int card6 = card5 + 1; card6 < 51; card6++)
            for (int card7 = card6 + 1; card7 < 52; card7++)
              result = intDict[32131]; // perform C(52,7) dictionary key lookups
sw.Stop();
Console.WriteLine("time for dictionary lookups: {0} ms", sw.ElapsedMilliseconds);

sw.Reset();

sw.Start();
for (int card1 = 0; card1 < 46; card1++)
  for (int card2 = card1 + 1; card2 < 47; card2++)
    for (int card3 = card2 + 1; card3 < 48; card3++)
      for (int card4 = card3 + 1; card4 < 49; card4++)
        for (int card5 = card4 + 1; card5 < 50; card5++)
          for (int card6 = card5 + 1; card6 < 51; card6++)
            for (int card7 = card6 + 1; card7 < 52; card7++)
              result = intList[32131]; // perform C(52,7) array index lookups
sw.Stop();
Console.WriteLine("time for array index lookups: {0} ms", sw.ElapsedMilliseconds);

que produce:

time for dictionary lookups: 2532 ms
time for array index lookups: 313 ms

¿Se espera este tipo de comportamiento (disminución del rendimiento en un factor de 8)? IIRC, un diccionario tiene, en promedio, búsquedas en O (1), mientras que una matriz tiene búsquedas en O (1) en el peor de los casos, por lo que espero que las búsquedas de matriz sean más rápidas, ¡pero no tanto!

Actualmente estoy almacenando clasificaciones de manos de póker en un Diccionario. Supongo que si esto es tan rápido como pueden ser las búsquedas en el diccionario, tengo que repensar mi enfoque y usar matrices en su lugar, aunque indexar las clasificaciones será un poco complicado y probablemente tendré que hacer otra pregunta al respecto.

Answer 1

¿Se espera este tipo de comportamiento (disminución del rendimiento en un factor de 8)?

Por qué no? Cada búsqueda de matriz es casi intantánea / insignificante, mientras que una búsqueda de diccionario puede necesitar al menos una llamada de subrutina adicional.

El punto de que ambos sean O (1) significa que incluso si tiene 50 veces más elementos en cada colección, la disminución del rendimiento es solo un factor de lo que sea (8).

Answer 2

Algo podría tomar un milenio y seguir siendo O (1).

Si realiza un solo paso a través de este código en la ventana de desmontaje, rápidamente llegará a comprender cuál es la diferencia.

Answer 3

Bienvenido a la notación Big-O. Siempre hay que tener en cuenta que hay un factor constante involucrado.

Hacer una búsqueda de dictado es, por supuesto, mucho más costoso que una búsqueda de matriz.

Big-O solo te dice cómo escalan los algoritmos. Duplique la cantidad de búsquedas y vea cómo cambian los números: ambos deben tomar alrededor del doble de tiempo.

Answer 4

El costo de recuperar un elemento de un Diccionario es O (1) , pero eso se debe a que el diccionario se implementa como una tabla hash, por lo que primero debe calcular el valor hash para saber qué elemento devolver. Las tablas hash a menudo no son tan eficientes, pero son buenas para conjuntos de datos grandes o conjuntos de datos que tienen muchos valores de hash únicos.

La lista (¡además de ser una palabra de basura utilizada para distribuir una matriz en lugar de una lista vinculada!) Será más rápida ya que devolverá el valor al calcular directamente el elemento que desea que se devuelva.

Answer 5

Las estructuras de diccionario son más útiles cuando el espacio clave es muy grande y no se puede asignar en un orden estable y secuenciado. Si puede convertir sus claves en un entero simple en un rango relativamente pequeño, será difícil encontrar una estructura de datos que funcione mejor que una matriz.

En una nota de implementación; En .NET, los diccionarios son esencialmente hashables. Puede mejorar un poco su rendimiento de búsqueda de claves asegurándose de que sus claves se agrupen en un gran espacio de valores únicos. Parece que en su caso, está utilizando un entero simple como una clave (que creo que hashes a su propio valor), por lo que puede ser lo mejor que puede hacer.

Answer 6

No olvide que las notaciones Big-O solo dicen cómo crece la complejidad con respecto al tamaño (etc.), no da ninguna indicación de los factores constantes involucrados. Es por eso que a veces incluso una búsqueda lineal de claves es más rápida que una búsqueda por diccionario, cuando hay suficientes pocas claves. Sin embargo, en este caso ni siquiera está haciendo una búsqueda con la matriz, solo una operación de indexación directa.

Para búsquedas directas en el índice, los arreglos son básicamente ideales, es solo un caso de

pointer_into_array = base_pointer + offset * size

(Y luego una desreferencia de puntero.)

Realizar una búsqueda en el diccionario es relativamente complicado: muy rápido en comparación con (digamos) una búsqueda lineal por clave cuando hay muchas claves, pero mucho más complicado que una búsqueda de matriz directa. Tiene que calcular el hash de la clave, luego determinar en qué grupo debería estar, posiblemente manejar hashes duplicados (o grupos duplicados) y luego verificar la igualdad.

Como siempre, elija la estructura de datos correcta para el trabajo, y si realmente puede salirse solo con la indexación en una matriz (o List<T> ), entonces sí, eso será increíblemente rápido.

Answer 7

Una búsqueda de matriz es lo más rápido que puede hacer, básicamente, todo lo que es es un bit de aritmética de punteros para ir desde el inicio de la matriz hasta el elemento que desea encontrar. Por otro lado, es probable que la búsqueda en el diccionario sea un poco más lenta, ya que necesita hacer hash y preocuparse por encontrar el grupo correcto. Aunque el tiempo de ejecución esperado también es O (1), las constantes algorítmicas son mayores, por lo que serán más lentas.