Dizionario basato su disco Python

Question

Stavo eseguendo un codice di programmazione dinamica (tentando di forzare la forza bruta confutare la congettura di Collatz = P) e stavo usando un dict per memorizzare le lunghezze delle catene che avevo già calcolato. Ovviamente, a un certo punto è rimasto senza memoria. Esiste un modo semplice per utilizzare una variante di un dict che sfoglia le parti di se stesso su disco quando si esaurisce lo spazio? Ovviamente sarà più lento di un dict in memoria, e probabilmente finirà per consumare il mio spazio sul disco rigido, ma questo potrebbe applicarsi ad altri problemi che non sono così inutili.

Mi sono reso conto che un dizionario basato su disco è praticamente un database, quindi ne ho implementato manualmente uno usando sqlite3, ma non l'ho fatto in modo intelligente e ho cercato ogni elemento nel DB uno alla volta ... era circa 300 volte più lento.

È il modo più intelligente di creare il mio set di dadi, conservarne solo uno alla volta e cercarli in modo efficiente?

Answer 1

L'hash-on-disk è generalmente indirizzato con Berkeley DB o qualcosa di simile - diverse opzioni sono elencate in Documentazione sulla persistenza dei dati Python . Puoi affrontarlo con una cache in memoria, ma prima verificherei le prestazioni native; con la memorizzazione nella cache del sistema operativo in atto potrebbe venire fuori allo stesso modo.

Answer 2

Vale la pena dare un'occhiata anche al modulo di terze parti shove . È molto simile a accantonare in quanto è un semplice oggetto simile a un dict, tuttavia può archiviare in vari backend (come file, SVN e S3), fornisce una compressione opzionale ed è anche sicuro per i thread. È un modulo molto utile

from shove import Shove

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

file_store['key'] = value

Answer 3

L'ultima volta che ho dovuto affrontare un problema come questo, ho riscritto per utilizzare SQLite anziché un dict e ho avuto un notevole aumento delle prestazioni. Tale aumento delle prestazioni era almeno in parte dovuto alle capacità di indicizzazione del database; a seconda dei tuoi algoritmi, YMMV.

Un wrapper sottile che esegue query SQLite in __getitem__ e __setitem__ non è molto codice da scrivere.

Answer 4

Il modulo shelve può farlo; in ogni caso, dovrebbe essere semplice da testare. Invece di:

self.lengths = {}

fare:

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

L'unico problema è che le chiavi degli scaffali devono essere stringhe, quindi dovrai sostituirle

self.lengths[indx]

con

self.lengths[str(indx)]

(Suppongo che le tue chiavi siano solo numeri interi, come da tuo commento al post di Charles Duffy)

Non c'è cache integrata nella memoria, ma il tuo sistema operativo potrebbe farlo per te comunque.

[in realtà, non è del tutto vero: è possibile passare l'argomento 'writeback = True' al momento della creazione. L'intento è quello di assicurarsi che l'archiviazione di elenchi e altre cose mutabili nello scaffale funzioni correttamente. Ma un effetto collaterale è che l'intero dizionario è memorizzato nella cache. Dal momento che questo ti ha causato problemi, probabilmente non è una buona idea :-)]

Answer 5

Con un po 'di pensiero sembra che potresti ottenere il modulo shelve per fare quello che vuoi.

Answer 6

Ho letto che pensi che shelve sia troppo lento e che hai provato a hackerare il tuo dict usando sqlite.

Anche un altro ha fatto questo:

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

Sembra piuttosto efficiente (e sebsauvage è un programmatore abbastanza buono). Forse potresti provarlo?

Answer 7

leggi la risposta per questa domanda da GvR;) Ordinamento di un milione di numeri interi a 32 bit in 2 MB di RAM usando Python

Answer 8

Dovresti portare più di un oggetto alla volta se c'è qualche euristica a sapere quali sono gli oggetti più probabili da recuperare in seguito, e non dimenticare gli indici come menziona Charles.

Answer 9

Non l'ho ancora provato ma Hamster DB è promettente e ha un'interfaccia Python.