practicas - Mejora del rendimiento del diccionario muy grande en Python

practicas python

Question

Me parece que si inicializo un diccionario vacío al principio y luego agrego elementos al diccionario en un bucle for (alrededor de 110,000 teclas, el valor de cada tecla es una lista, que también aumenta en el bucle), la velocidad disminuye como para el lazo va.

Sospecho que el problema es que el diccionario no sabe el número de teclas en el momento de la inicialización y no está haciendo algo muy inteligente, por lo que quizás la colisión de almacenamiento se produzca con bastante frecuencia y se ralentice.

Si conozco la cantidad de claves y cuáles son exactamente esas claves, ¿hay alguna forma en python para hacer que un dict (o una tabla hash) funcione de manera más eficiente? Recuerdo vagamente que si conoces las teclas, puedes diseñar la función hash inteligentemente (hash perfecto?) Y asignar el espacio de antemano.

Answer 1

Si conozco la cantidad de claves y cuáles son exactamente esas claves, ¿hay alguna forma en python para hacer que un dict (o una tabla hash) funcione de manera más eficiente? Recuerdo vagamente que si conoces las teclas, puedes diseñar la función hash inteligentemente (hash perfecto?) Y asignar el espacio de antemano.

Python no expone una opción de ajuste de tamaño para acelerar la "fase de crecimiento" de un diccionario, ni proporciona ningún control directo sobre la "ubicación" en el diccionario.

Dicho esto, si las claves siempre se conocen de antemano, puede almacenarlas en un set y construir sus diccionarios desde el conjunto utilizando dict.fromkeys() . Ese método de clase está optimizado para pre-dimensionar el diccionario en función del tamaño del conjunto y puede llenar el diccionario sin nuevas llamadas a __hash __ ():

>>> keys = {''red'', ''green'', ''blue'', ''yellow'', ''orange'', ''pink'', ''black''}
>>> d = dict.fromkeys(keys)  # dict is pre-sized to 32 empty slots

Si su objetivo es reducir las colisiones, puede ejecutar experimentos en el orden de inserción en el diccionario para minimizar las acumulaciones. (Eche un vistazo a la variación de Brent en el Algoritmo D en el TAOCP de Knuth para tener una idea de cómo se hace esto).

Al instrumentar un modelo de Python puro para diccionarios (como este ), es posible contar el promedio ponderado de sondeos para un orden de inserción alternativo. Por ejemplo, insertar dict.fromkeys([11100, 22200, 44400, 33300]) promedia 1,75 sondeos por búsqueda. Eso supera las 2.25 sondas promedio por búsqueda para dict.fromkeys([33300, 22200, 11100, 44400]) .

Otro "truco" es aumentar la reserva en un diccionario completamente poblado al engañarlo para que aumente su tamaño sin agregar nuevas claves :

 d = dict.fromkeys([''red'', ''green'', ''blue'', ''yellow'', ''orange''])
 d.update(dict(d))     # This makes room for additional keys
                       # and makes the set collision-free.

Por último, puede introducir su propia __hash __ () personalizada para sus claves con el objetivo de eliminar todas las colisiones (tal vez utilizando un generador de hash perfecto como gperf ).