Mejora del rendimiento de un diccionario muy grande en Python

Encuentro que si inicializo un diccionario vacío al principio y luego agrego elementos al diccionario en un bucle for (alrededor de 110,000 claves, el valor de cada clave es una lista, que también aumenta en el bucle), la velocidad disminuye a medida que para el bucle va.

Sospecho que el problema es que el diccionario no conoce la cantidad de claves en el momento de inicio y no está haciendo algo muy inteligente, por lo que tal vez la colisión de almacenamiento sea bastante frecuente y se ralentice.

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

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

Python no expone una opción de tamaño previo 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 conjunto y construir sus diccionarios a partir del conjunto utilizando dict.fromkeys () . Ese método de clase está optimizado para pre-dimensionar el diccionario según el tamaño establecido y puede poblar 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 objective es reducir las colisiones, puede realizar experimentos en el orden de inserción en el diccionario para minimizar las acumulaciones. (Eche un vistazo a la variación de Brent sobre 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 número promedio ponderado de sondas para un orden de inserción alternativo. Por ejemplo, al insertar dict.fromkeys([11100, 22200, 44400, 33300]) promedian 1.75 sondas por búsqueda. Eso supera las 2.25 sondas promedio por búsqueda de dict.fromkeys([33300, 22200, 11100, 44400]) .

Otro “truco” es boost el conocimiento en un diccionario completamente poblado engañándolo para que aumente su tamaño sin agregar nuevas claves s:

  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 propio __hash __ () personalizado para sus claves con el objective de eliminar todas las colisiones (quizás utilizando un generador de hash perfecto como gperf ).