Diccionario basado en disco de Python

Question

Estaba ejecutando un código de programación dinámico (tratando de usar fuerza bruta para refutar 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 va a colocar partes de sí mismo en el disco cuando se quede sin espacio? Obviamente, será más lento que un dict en memoria, y probablemente terminará consumiendo mi 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 prácticamente una base de datos, así que implementé manualmente uno usando sqlite3, pero no lo hice de ninguna manera inteligente y tuve que buscar cada elemento en el DB en una tiempo ... fue aproximadamente 300 veces más lento.

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

Answer 1

Hash-on-disk se trata generalmente con Berkeley DB o algo similar; hay varias opciones en el Python Data Persistence documentation. Puede afrontarlo con un caché en memoria, pero probaría primero el rendimiento nativo; con el almacenamiento en caché del sistema operativo en su lugar, podría salir más o menos igual.

Answer 2

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

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

Answer 3

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

Answer 4

Con un poco de reflexión, parece que podría obtener el shelve module para hacer lo que quiera.

Answer 5

El módulo shelve puede hacerlo; de todos modos, debería ser simple de probar. En lugar de:

self.lengths = {} 

hacer:

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

El único inconveniente es que las claves a los estantes deben ser cadenas, por lo que tendrá que reemplazar

self.lengths[indx] 

con

self.lengths[str(indx)] 

(supongo que tus llaves son solo yo ntegers, según su comentario a la publicación de Charles Duffy)

No hay memoria caché incorporada en la memoria, pero su sistema operativo puede hacer eso por usted de todos modos.

[en realidad, eso no es del todo cierto: puede 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 está almacenado en la memoria.Como esto le causó problemas, probablemente no sea una buena idea :-)]

Answer 6

El módulo de la tercera parte shove también vale la pena echarle un vistazo. Es muy similar a shelve porque es un objeto simple parecido a un dictado, sin embargo, puede almacenarse en varios backends (como archivos, SVN y S3), proporciona compresión opcional e incluso es seguro para los hilos. Es un módulo muy práctico

from shove import Shove 

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

file_store['key'] = value 

Answer 7

no lo probé todavía, pero Hamster DB es prometedora y tiene una interfaz de Python.

Answer 8

respuesta de lectura para esta pregunta desde RGv;) Sorting a million 32-bit integers in 2MB of RAM using Python

Answer 9

He leído usted piensa dejar de lado es demasiado lento y se trató de cortar su propio dict usando SQLite.

Otra hicieron esto también:

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

Parece bastante eficiente (y sebsauvage es un muy buen programador). ¿Tal vez podrías intentarlo?