Optimización de búsquedas:Búsquedas de claves de diccionario vs.Búsquedas de índices de matriz

Question

Estoy escribiendo un evaluador de manos de póquer de 7 cartas como uno de mis proyectos favoritos.Mientras intentaba optimizar su velocidad (me gusta el desafío), me sorprendió descubrir que el rendimiento de las búsquedas de claves del 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 las 52 manos de elegir 7 = 133,784,560 posibles de 7 cartas:

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 O(1), mientras que una matriz tiene búsquedas 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óquer 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

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

Para búsquedas de índices directas, las matrices son básicamente ideales; es sólo un caso de

pointer_into_array = base_pointer + offset * size

(Y luego una desreferencia de puntero).

Realizar una búsqueda en un 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 directa en una matriz.Tiene que calcular el hash de la clave, luego determinar en qué depósito debería estar, posiblemente tratar con hashes duplicados (o depósitos duplicados) y luego verificar la igualdad.

Como siempre, elija la estructura de datos adecuada para el trabajo, y si realmente puede salirse con la suya simplemente indexando en una matriz (o List<T>) entonces sí, será increíblemente rápido.

Answer 2

  

¿Es este tipo de comportamiento esperado (rendimiento disminución en un factor de 8)?

¿Por qué no? Cada consulta de matriz es casi intantaneous / despreciable, mientras que una búsqueda de diccionario puede necesitar al menos una llamada de subrutina adicional.

El punto de su ser tanto O (1) significa que incluso si usted tiene 50 veces más artículos en cada colección, la disminución del rendimiento es todavía sólo un factor de lo que sea (8).

Answer 3

Algo podría tomar un milenio, y todavía ser O (1).

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

Answer 4

estructuras diccionario son más útiles cuando el espacio de claves es muy grande y no puede ser asignada a una estable, orden secuenciado. Si usted puede convertir sus llaves en un simple número entero en un rango relativamente pequeño, se le apuros para encontrar una estructura de datos que se obtienen mejores resultados que una matriz.

En una nota de aplicación; en .NET, los diccionarios son esencialmente hashables. Puede mejorar algo su rendimiento clave de búsqueda, asegurando que sus claves hash en un gran espacio de valores únicos. Parece que, en su caso, se utiliza un número entero simple como una llave (que creo que los hashes a su propio valor) -. Por lo que puede ser lo mejor que puede hacer

Answer 5

Una consulta de matriz es sobre la cosa más rápida que puede hacer - esencialmente todo lo que es es un solo bit de la aritmética de punteros para ir desde el inicio de la matriz para el elemento que desea encontrar. Por otro lado, la búsqueda de diccionario es probable que sea un poco más lento, ya que tiene que hacer hash y ocuparse de encontrar el cubo correcto. Aunque el tiempo de ejecución esperado es también O (1) - las constantes algorítmicos son mayores por lo que será más lento

.

Answer 6

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

Hacer una Dict-Lookup es por supuesto mucho más caro que una búsqueda de matriz.

Big-O sólo le dice cómo escala algoritmos. El doble de la cantidad de operaciones de búsqueda y ver cómo cambian los números:. Ambos deben tener todo el tiempo dos veces

Answer 7

El costo de la recuperación de un elemento de una de diccionario es O (1) , pero eso es porque un diccionario se implementa como una tabla hash - lo que tiene que calcular primero el valor hash para saber qué elemento para volver. Tablas hash a menudo no son tan eficientes - pero son buenos para grandes conjuntos de datos o conjuntos de datos que tienen una gran cantidad de valores únicos en hash

.

La lista (aparte de ser una palabra usada para la basura dercribe una matriz en lugar de una lista enlazada!) Será más rápido, ya que devolverá el valor calculando directamente el elemento que desea obtener.