Eficiencia de memoria: ¿un diccionario grande o un diccionario de diccionarios más pequeños?

Question

Estoy escribiendo una aplicación en Python (2.6) que requiere que use un diccionario como almacén de datos.

Tengo curiosidad acerca de si es o no más eficiente con la memoria tener un diccionario grande, o dividirlo en muchos diccionarios (mucho) más pequeños, luego tener un diccionario "índice" que contiene una referencia a todos los diccionarios más pequeños.

Sé que hay un montón de sobrecarga en general con listas y diccionarios. Leí en algún lugar que Python internamente asigna suficiente espacio que el diccionario/lista de elementos a la potencia de 2.

Soy lo suficientemente nuevo para python que no estoy seguro si hay otras complicaciones/sorpresas internas inesperadas como eso, eso no es evidente para el usuario promedio que debería tener en cuenta.

Una de las dificultades es saber cómo el poder del sistema 2 cuenta "elementos". ¿Cada tecla: par se cuenta como 1 artículo? Parece importante saberlo porque si tienes un diccionario monolítico de 100 elementos, se asignarán 100^2 ítems. Si tiene 100 diccionarios de elementos individuales (1 clave: par), entonces cada diccionario solo tendrá una asignación de 1^2 (también conocido como asignación no adicional).

¡Cualquier información claramente presentada sería muy útil!

Answer 1

tres sugerencias:

1. Use un diccionario.
   Es más fácil, es más sencillo, y alguien más ya ha optimizado este problema para usted. Hasta que no hayas medido realmente tu código y haya rastreado un problema de rendimiento en esta parte del mismo, no tienes ninguna razón para no hacer lo simple y directo.

2. Optimizar más tarde.
   Si usted es realmente preocupado por el rendimiento, entonces resuma el problema, haga una clase para envolver cualquier mecanismo de búsqueda que termine usando y escriba su código para usar esta clase. Puede cambiar la implementación más adelante si encuentra que necesita alguna otra estructura de datos para un mayor rendimiento.

3. Lectura en tablas hash.
   Los diccionarios son hash tables, y si está preocupado acerca de su tiempo o sobrecarga de espacio, debería leer sobre cómo se implementan. Esto es ciencia de la computación básica. El corto de él es que las tablas hash son:

   • caso medio O (1) Tiempo de de búsqueda
   • O (n) espacio (esperar sobre 2n, dependiendo de varios parámetros)

   No sé dónde ha leído que eran O (n^2) espacio, pero si lo fueran, entonces no serían de uso generalizado, como lo son en la mayoría de los idiomas de hoy. Hay dos ventajas de estas propiedades agradables de tablas hash:

   1. O (1) tiempo de búsqueda implica que no tendrá que pagar un costo en tiempo de búsqueda por tener un diccionario más grande, como las operaciones de búsqueda de tiempo no depende en el tamaño.
   2. O (n) espacio implica que no obtendrá mucho de nada, desde dividir el diccionario en partes más pequeñas. El espacio se escala linealmente con el número de elementos, por lo que muchos diccionarios pequeños no ocuparán mucho menos espacio que uno grande o viceversa. Esto no sería cierto si fueran O (n^2) espacio, pero por suerte para ti, no lo son.

   Éstos son algunos recursos más que podrían ayudar:

   • El Wikipedia article on Hash Tables da una gran lista de los diversos esquemas de búsqueda y asignación utilizados en tablas hash.
   • El GNU Scheme documentation tiene una buena discusión de la cantidad de espacio que puede esperar tablas hash que ocupan, incluyendo una discusión formal de por qué "la cantidad de espacio utilizado por la tabla de dispersión es proporcional al número de asociaciones en la tabla" . Esto podría interesarte.

   Aquí hay algunas cosas que usted podría considerar si encuentra que realmente necesita para optimizar su aplicación diccionario:

   • Aquí está el código fuente en C para los diccionarios de Python, en caso de que quiera todos los detalles. Hay abundante documentación aquí:
     • dictobject.h
     • dictobject.c
   • Aquí es una python implementation de que, en caso de que no le gusta leer C.
     (Gracias a Ben Peterson)
   • El Java Hashtable class docs habla un poco sobre cómo funcionan los factores de carga y cómo afectan el espacio que ocupa tu hash. Tenga en cuenta que hay una compensación entre su factor de carga y la frecuencia con la que necesita rehash. Las repeticiones pueden ser costosas.

Answer 2

Muchas veces, los diccionarios de diccionarios son útiles por motivos que no sean de rendimiento. es decir, le permiten almacenar información de contexto sobre los datos sin tener campos adicionales en los objetos mismos, y hacer que los subconjuntos de consulta de los datos sean más rápidos.

En términos de uso de la memoria, sería lógico pensar que un diccionario grande usará menos RAM que múltiples más pequeños. Recuerde, si está anidando diccionarios, cada capa adicional de anidación duplicará aproximadamente la cantidad de diccionarios que necesita asignar.

En términos de velocidad de consulta, múltiples dicts tomarán más tiempo debido al mayor número de búsquedas requeridas.

Así que creo que la única manera de responder a esta pregunta es que usted perfile su propio código. Sin embargo, mi sugerencia es utilizar el método que hace que su código sea el más limpio y fácil de mantener. De todas las características de Python, los diccionarios son probablemente los más ajustados para un rendimiento óptimo.

Answer 3

Si está usando Python, realmente no debería preocuparse por este tipo de cosas en primer lugar. Simplemente construya su estructura de datos de la manera que mejor se adapte a sus necesidades de, no las de la computadora.

Esto huele a optimización prematura, no mejora de rendimiento. Haga un perfil de su código si algo realmente obstaculiza el acceso, pero hasta entonces, simplemente deje que Python haga lo que hace y concéntrese en la tarea de programación real, y no en la mecánica subyacente.

Answer 4

"Simple" es generalmente mejor que "inteligente", especialmente si no tiene un motivo probado para ir más allá de "simple". Y, de todos modos, "Memoria eficiente" es un término ambiguo, y hay compensaciones, cuando se considera la persistencia, la serialización, la caché, el intercambio y un montón de otras cosas que alguien más ya ha pensado para que en la mayoría de los casos no lo haga Necesitar.

Piensa "La forma más sencilla de manejarlo correctamente" optimiza mucho más tarde.

Answer 5

Honestamente, no podrá notar la diferencia de ninguna manera, en términos de rendimiento o uso de la memoria.A menos que tenga que lidiar con decenas de millones de elementos o más, el rendimiento o el impacto de la memoria es solo ruido.

Por la forma en que redactó su segunda oración, parece que el primer diccionario es su primera inclinación, y coincide más estrechamente con el problema que está tratando de resolver. Si eso es cierto, ve con eso. Lo que encontrará sobre Python es que las soluciones que todos consideran "correctas" casi siempre resultan ser aquellas que son lo más claras y simples posible.

Answer 6

optimización prematura bla bla, no lo hagas bla bla.

Creo que está equivocado acerca de la potencia de dos asignaciones adicionales. Creo que es solo un multiplicador de dos. x * 2, no x^2.

He visto esta pregunta algunas veces en varias listas de correo de Python.

En cuanto a la memoria, aquí es una versión parafraseada de un tal debate (el puesto en cuestión quería almacenar cientos de millones de números enteros):

1. Un conjunto() es más eficiente del espacio de un dict() , si solo desea probar la membresía
2. gmpy tiene una clase de tipo bitvector para almacenar conjuntos densos de enteros
3. Los dic se mantienen entre 50% y 30% vacíos, y una entrada es aproximadamente ~ 12 bytes (aunque el verdadero la cantidad variará según la plataforma un poco).

Así, cuantos menos objetos tenga, menos memoria va a utilizar y menos búsquedas va a hacer (ya que tendrá que buscar en el índice, luego un segundo búsqueda en el valor real).

Como otros, dijo, perfil para ver sus cuellos de botella. Mantener un conjunto de miembros() y un valor de dict() puede ser más rápido, pero utilizará más memoria.

También sugiero reenviar esto a una lista específica de python, como comp.lang.python, que está lleno de gente mucho más conocedora que yo que le daría todo tipo de información útil.

Answer 7

Si su diccionario es tan grande que no cabe en la memoria, es posible que desee echar un vistazo a ZODB, una base de datos de objetos muy maduro para Python.

La 'raíz' de la base de datos tiene la misma interfaz que un diccionario, y no necesita cargar toda la estructura de datos en la memoria a la vez, p. puede iterar sobre solo una parte de la estructura al proporcionar las teclas de inicio y fin.

También proporciona transacciones y control de versiones.