Diccionario basado en disco de Python

StackOverflow https://stackoverflow.com/questions/226693

Pregunta

Estaba ejecutando un código de programación dinámica (tratando de refutar con fuerza bruta la conjetura de Collatz = P) y estaba usando un dict para almacenar las longitudes de las cadenas que ya había calculado. Obviamente, se quedó sin memoria en algún momento. ¿Hay alguna manera fácil de usar alguna variante de un dict que se saldrá de las partes de sí mismo en el disco cuando se quede sin espacio? Obviamente, será más lento que un dictado en memoria, y probablemente terminará consumiendo espacio en el disco duro, pero esto podría aplicarse a otros problemas que no son tan inútiles.

Me di cuenta de que un diccionario basado en disco es más o menos una base de datos, así que implementé manualmente uno usando sqlite3, pero no lo hice de ninguna manera inteligente e hice que buscara cada elemento en la base de datos uno por uno. ... fue aproximadamente 300x más lento.

¿Es la forma más inteligente de crear mi propio conjunto de dictados, manteniendo solo uno en la memoria a la vez, y pagándolos de una manera eficiente?

¿Fue útil?

Solución

Hash-on-disk generalmente se trata con Berkeley DB o algo similar: varias opciones se enumeran en Documentación de persistencia de datos de Python . Puedes enfrentarlo con un caché en memoria, pero primero probaría contra el rendimiento nativo; con el almacenamiento en caché del sistema operativo en su lugar, podría salir casi igual.

Otros consejos

El módulo shove de terceros también vale la pena echarle un vistazo. Es muy similar a dejar de lado porque es un simple objeto similar a un dict, sin embargo, puede almacenar varios backends (como archivo, SVN y S3), ofrece compresión opcional e incluso es seguro para subprocesos. Es un módulo muy útil 

from shove import Shove

mem_store = Shove()
file_store = Shove('file://mystore')

file_store['key'] = value

La última vez que enfrenté un problema como este, reescribí para usar SQLite en lugar de un dict, y tuve un aumento masivo de rendimiento. Ese aumento de rendimiento se debió, al menos parcialmente, a las capacidades de indexación de la base de datos; Dependiendo de sus algoritmos, YMMV.

Una envoltura delgada que realiza consultas SQLite en __getitem__ y __setitem__ no es mucho código para escribir.

El módulo shelve puede hacerlo; En cualquier caso, debería ser fácil de probar. En lugar de: 

self.lengths = {}

hacer: 

import shelve
self.lengths = shelve.open('lengths.shelf')

El único problema es que las llaves de los estantes deben ser cadenas, por lo que tendrás que reemplazarlas 

self.lengths[indx]

con 

self.lengths[str(indx)]

(Supongo que tus claves son solo enteros, según tu comentario a la publicación de Charles Duffy)

No hay caché incorporado en la memoria, pero tu sistema operativo puede hacer eso por ti de todos modos.

[en realidad, eso no es del todo cierto: puedes pasar el argumento 'writeback = True' en la creación. La intención de esto es asegurarse de que las listas de almacenamiento y otras cosas mutables en el estante funcionen correctamente. Pero un efecto secundario es que todo el diccionario se almacena en la memoria caché. Dado que esto le causó problemas, probablemente no sea una buena idea :-)]

Con un poco de pensamiento, parece que podrías obtener el módulo de almacenamiento para hacer lo que quieras.

He leído que piensas que Shelve es demasiado lento y que intentaste hackear tu propio dictado usando sqlite.

Otro también hizo esto:

http://sebsauvage.net/python/snyppets/index.html#dbdict

Parece bastante eficiente (y sebsauvage es un codificador bastante bueno). Tal vez podrías darle una oportunidad?

Debería traer más de un elemento a la vez si hay alguna heurística para saber cuáles son los elementos que más probablemente se recuperarán a continuación, y no olvide los índices como los que menciona Charles.

No lo probé todavía, pero Hamster DB es prometedor y tiene una interfaz Python.

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top