Dictionnaire basé sur disque Python

Question

J'utilisais un code de programmation dynamique (essayant de brider par la force pour réfuter la conjecture de Collatz = P) et j'utilisais un dict pour stocker les longueurs des chaînes que j'avais déjà calculées. De toute évidence, il n'y avait plus de mémoire à un moment donné. Existe-t-il un moyen simple d’utiliser une variante d’un dict qui lira des parties de lui-même sur le disque s’il n’ya plus assez de place? Évidemment, ce sera plus lent qu'un dicton en mémoire, et cela finira probablement par occuper l’espace libre sur mon disque dur, mais cela pourrait s’appliquer à d’autres problèmes qui ne sont pas si futiles.

J'ai réalisé qu'un dictionnaire sur disque est une base de données. Je l'ai donc implémenté manuellement à l'aide de sqlite3, mais je ne l'ai pas fait intelligemment et je l'ai fait rechercher chaque élément de la base de données à la fois. ... il était environ 300 fois plus lent.

Est-ce le moyen le plus intelligent de créer mon propre jeu de dict, en ne gardant qu’un en mémoire à la fois, et de les rechercher de manière efficace?

Answer 1

Le hachage sur disque est généralement traité avec Berkeley DB ou quelque chose de similaire - plusieurs options sont répertoriées dans Documentation Python Data Persistence . Vous pouvez l'avoir avec un cache en mémoire, mais je testerais d'abord avec les performances natives; avec la mise en cache du système d’exploitation en place, il pourrait en résulter à peu près le même.

Answer 2

Le module shove proposé par une tierce partie mérite également une attention particulière. Cela ressemble beaucoup à shelve en ce qu’il s’agit d’un objet simple, semblable à un dicton. Toutefois, il peut être stocké dans différents systèmes de traitement (tels que fichier, SVN et S3), offre une compression facultative et protège même les threads. C'est un module très pratique

from shove import Shove

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

file_store['key'] = value

Answer 3

La dernière fois que je rencontrais un problème comme celui-ci, j’ai réécrit pour utiliser SQLite plutôt qu’un dict, et mes performances ont été considérablement améliorées. Cette augmentation des performances s'explique au moins en partie par les capacités d'indexation de la base de données; en fonction de vos algorithmes, YMMV.

Un wrapper fin qui effectue les requêtes SQLite dans __ getitem __ et __ setitem __ n'a pas beaucoup de code à écrire.

Answer 4

Le module shelve peut le faire; en tout cas, il devrait être simple à tester. Au lieu de:

self.lengths = {}

faire:

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

Le seul problème est que les clés des étagères doivent être des chaînes, vous devrez donc les remplacer

.

self.lengths[indx]

avec

self.lengths[str(indx)]

(Je suppose que vos clés ne sont que des entiers, conformément à votre commentaire au message de Charles Duffy)

Il n'y a pas de cache intégré en mémoire, mais votre système d'exploitation peut le faire pour vous quand même.

[en fait, ce n'est pas tout à fait vrai: vous pouvez passer l'argument 'writeback = True' à la création. Le but de cette opération est de s’assurer que le stockage des listes et d’autres éléments modifiables dans l’étagère fonctionne correctement. Mais un effet secondaire est que tout le dictionnaire est mis en cache dans la mémoire. Puisque cela vous a causé des problèmes, ce n’est probablement pas une bonne idée :-)]

Answer 5

Avec un peu de réflexion, il semblerait que vous puissiez obtenir le module shelve faire ce que vous voulez.

Answer 6

J'ai lu que vous pensiez que shelve était trop lent et que vous essayiez de pirater votre propre dict en utilisant sqlite.

Un autre l'a fait aussi:

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

Cela semble assez efficace (et sebsauvage est un très bon codeur). Peut-être pourriez-vous essayer?

Answer 7

lire la réponse à cette question de GvR;) Tri d'un million d'entiers 32 bits dans 2 Mo de RAM avec Python

Answer 8

Vous devriez apporter plusieurs éléments à la fois s'il existe une méthode heuristique pour savoir quels sont les éléments les plus susceptibles d'être récupérés, et n'oubliez pas les index tels que ceux mentionnés par Charles.

Answer 9

Je ne l'ai pas encore essayé, mais Hamster DB est prometteur et possède une interface Python.