Dicionário Python Disk-Based

Question

Eu estava correndo algum código de programação dinâmica (tentando de força bruta refutar a Collatz conjectura = P) e eu estava usando um dicionário para armazenar os comprimentos das cadeias Eu já tinha computados. Obviamente, ele ficou sem memória em algum ponto. Existe alguma maneira fácil de usar alguma variante de um dict que partes da página de si para o disco quando ele é executado fora da sala? Obviamente, ele será mais lento do que um dict in-memory, e provavelmente vai acabar comendo meu espaço no disco rígido, mas isso poderia se aplicar a outros problemas que não são tão fútil.

Eu percebi que um dicionário baseado em disco é praticamente um banco de dados, então eu implementado manualmente um usando sqlite3, mas eu não fazê-lo de qualquer maneira inteligente e tinha que olhar para cima cada elemento da DB um de cada vez ... foi cerca de 300x mais lento.

É a forma mais inteligente para apenas criar meu próprio conjunto de dicts, mantendo apenas um na memória de cada vez, e paginação-los de alguma maneira eficiente?

Answer 1

Hash-on-disk geralmente é abordada com Berkeley DB ou algo semelhante - opções de vários estão listados na Python persistência de dados documentação . Pode frente com um cache na memória, mas eu testar contra desempenho nativo em primeiro lugar; com a operação de cache do sistema no lugar que pode sair sobre o mesmo.

Answer 2

O 3o partido empurrão módulo também vale a pena dar uma olhada. É muito semelhante a arquivar na medida em que é um dicionário-como simples objeto, no entanto, ele pode armazenar vários backends (como arquivo, SVN, e S3), fornece a compressão opcional, e ainda é threadsafe. É um módulo muito útil

from shove import Shove

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

file_store['key'] = value

Answer 3

A última vez que eu estava enfrentando um problema como este, eu reescrevi a usar SQLite em vez de um dicionário, e teve um aumento de desempenho enorme. Esse aumento de desempenho foi pelo menos parcialmente por conta de recursos de indexação do banco de dados; dependendo de seus algoritmos, YMMV.

A fina capa que faz consultas SQLite em __getitem__ e __setitem__ não é muito código para escrever.

Answer 4

O prateleira módulo pode fazê-lo; de qualquer forma, deve ser simples para testar. Em vez de:

self.lengths = {}

fazer:

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

O único problema é que as chaves para prateleiras devem ser strings, assim você terá que substituir

self.lengths[indx]

com

self.lengths[str(indx)]

(estou assumindo suas chaves são apenas números inteiros, conforme o seu comentário ao post de Charles Duffy)

Não há nenhuma construído em cache na memória, mas seu sistema operacional pode fazer isso por você de qualquer maneira.

[na verdade, isso não é bem verdade: você pode passar o argumento de write-back = True 'na criação. A intenção deste é certificar-se listas de armazenamento e outras coisas mutáveis ??na prateleira funciona corretamente. Mas um efeito colateral é que todo o dicionário é armazenado em cache na memória. Uma vez que este causou problemas para você, ele provavelmente não é uma boa idéia :-)]

Answer 5

Com um pouco de pensamento, parece que você poderia obter o prateleira módulo para fazer o que quiser.

Answer 6

Eu li que você pensa prateleira é muito lento e você tentou cortar o seu próprio dict usando sqlite.

Outra fiz isso também:

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

Parece bastante eficiente (e sebsauvage é um bom codificador bonita). Talvez você poderia dar-lhe uma tentativa?

Answer 7

ler a resposta para esta pergunta de GvR;) Classificando um milhão de inteiros de 32 bits em 2MB de memória RAM usando Python

Answer 8

Você deve trazer mais de um item de cada vez, se há alguma heurística para saber quais são os itens mais prováveis ??de serem recuperados seguinte, e não se esqueça os índices como Charles menciona.

Answer 9

Eu não tentei ainda, mas Hamster DB é promissor e tem uma interface Python.