python - ¿Por qué las búsquedas de dict siempre son mejores que las búsquedas de lista?

performance optimization

Question

Estaba usando un diccionario como una tabla de búsqueda, pero comencé a preguntarme si una lista sería mejor para mi aplicación: la cantidad de entradas en mi tabla de búsqueda no era tan grande. Sé que las listas usan matrices C bajo el capó, lo que me hizo concluir que buscar en una lista con solo unos pocos elementos sería mejor que en un diccionario (acceder a algunos elementos en una matriz es más rápido que calcular un hash).

Decidí perfilar las alternativas, pero los resultados me sorprendieron. ¡La búsqueda de listas solo fue mejor con un solo elemento! Vea la siguiente figura (diagrama de registro y registro):

Así que aquí viene la pregunta: ¿Por qué las búsquedas de listas funcionan tan mal? ¿Qué me estoy perdiendo?

En una pregunta secundaria, otra cosa que me llamó la atención fue una pequeña "discontinuidad" en el tiempo de búsqueda de dict después de aproximadamente 1000 entradas. Tracé el tiempo de búsqueda de Dict solo para mostrarlo.

ps1 Sé acerca de O (n) vs O (1) tiempo amortizado para matrices y tablas hash, pero generalmente es el caso que para una pequeña cantidad de elementos iterar sobre una matriz es mejor que usar una tabla hash.

ps2 Aquí está el código que utilicé para comparar los tiempos de búsqueda de dict y list:

import timeit

lengths = [2 ** i for i in xrange(15)]

list_time = []
dict_time = []
for l in lengths:
    list_time.append(timeit.timeit(''%i in d'' % (l/2), ''d=range(%i)'' % l))
    dict_time.append(timeit.timeit(''%i in d'' % (l/2),
                                   ''d=dict.fromkeys(range(%i))'' % l))
    print l, list_time[-1], dict_time[-1]

ps3 Usando Python 2.7.13

Answer 1

Sé que las listas usan matrices C bajo el capó, lo que me hizo concluir que buscar en una lista con solo unos pocos elementos sería mejor que en un diccionario (acceder a algunos elementos en una matriz es más rápido que calcular un hash).

El acceso a algunos elementos de matriz es barato, claro, pero la computación == es sorprendentemente pesada en Python. ¿Ves ese pico en tu segundo gráfico? Ese es el costo de calcular == para dos ints allí mismo.

Tus búsquedas de lista necesitan calcular == mucho más que tus búsquedas dict.

Mientras tanto, los hash de computación pueden ser una operación bastante pesada para muchos objetos, pero para todos los involucrados aquí, simplemente se limitan a sí mismos. (-1 haría hash a -2, y los enteros grandes (técnicamente long s) harían hash a enteros más pequeños, pero eso no se aplica aquí).

La búsqueda de Dict no es realmente tan mala en Python, especialmente cuando tus claves son solo un rango consecutivo de entradas. Todas las entradas aquí se resumen a sí mismas, y Python usa un esquema de direccionamiento abierto personalizado en lugar de encadenar, por lo que todas las teclas terminan casi tan contiguas en la memoria como si hubieras usado una lista (es decir, los punteros a las teclas terminan en un rango contiguo de PyDictEntry s). El procedimiento de búsqueda es rápido, y en los casos de prueba, siempre toca la tecla derecha en la primera sonda.

De acuerdo, de vuelta a la espiga en el gráfico 2. El pico en los tiempos de búsqueda en 1024 entradas en el segundo gráfico es porque para todos los tamaños más pequeños, los enteros que estabas buscando eran todos <= 256, por lo que todos cayeron dentro del rango de Caché de enteros pequeños de CPython. La implementación de referencia de Python mantiene los objetos enteros canónicos para todos los enteros de -5 a 256, inclusive. Para estos enteros, Python pudo usar una comparación rápida de punteros para evitar pasar por el proceso (sorprendentemente pesado) de computación == . Para enteros más grandes, el argumento para in ya no era el mismo objeto que el entero coincidente en el dict, y Python tuvo que pasar por todo el proceso == .

Answer 2

La respuesta corta es que las listas usan búsqueda lineal y los dicts usan la búsqueda amortizada O (1).

Además, las búsquedas dict pueden omitir una prueba de igualdad cuando 1) los valores hash no coinciden o 2) cuando hay una coincidencia de identidad. Las listas solo se benefician de la identidad: implica la optimización de la igualdad.

En 2008, di una charla sobre este tema en la que encontrarás todos los detalles: https://www.youtube.com/watch?v=hYUsssClE94

Aproximadamente la lógica para buscar listas es:

for element in s:
    if element is target:
        # fast check for identity implies equality
        return True
    if element == target:
        # slower check for actual equality
        return True
return False

Para dicts, la lógica es más o menos:

h = hash(target)
for i in probe_sequence(h, len(table)):
    element = key_table[i]
    if element is UNUSED:
        raise KeyError(target)
    if element is target:
        # fast path for identity implies equality
        return value_table[i]
    if h != h_table[i]:
        # unequal hashes implies unequal keys
        continue
    if element == target:
        # slower check for actual equality
        return value_table[i]

Las tablas hash de diccionario suelen estar entre un tercio y dos tercios llenas, por lo que tienden a tener pocas colisiones (pocos viajes alrededor del ciclo que se muestra arriba) independientemente del tamaño. Además, la comprobación del valor hash evita las verificaciones de igualdad innecesarias y lentas (la posibilidad de un control de igualdad desperdiciado es aproximadamente 1 en 2 ** 64).

Si tu tiempo se centra en enteros, también hay otros efectos en juego. Ese hash de un int es el int en sí mismo, por lo que hashing es muy rápido. Además, significa que si está almacenando números enteros consecutivos, no suele haber colisiones.

Answer 3

Usted dice "acceder a algunos elementos en una matriz es más rápido que calcular un hash".

Una simple regla de hash para cadenas puede ser solo una suma (con un módulo al final). Esta es una operación sin sucursales que se puede comparar favorablemente con las comparaciones de caracteres, especialmente cuando hay una coincidencia larga en el prefijo.