Dictionnaire sur disque Python

Question

J'ai été l'exécution de certains de programmation dynamique de code (en essayant de forcer réfuter la conjecture de Collatz =P) et j'ai été en utilisant un dictionnaire pour stocker les longueurs des chaînes que j'avais déjà calculé. De toute évidence, il a manqué de mémoire à un certain point. Est-il un moyen facile d'utiliser la variante d'une dict qui va de la page de parties de lui-même sur le disque quand il est à court de chambre? Évidemment, il sera plus lent qu'un mémoire dict, et il va probablement jusqu'à la fin de manger mon espace sur le disque dur, mais cela pourrait s'appliquer à d'autres problèmes qui ne sont pas si futile.

J'ai réalisé qu'un disque dictionnaire est à peu près d'une base de données, j'ai donc mis en œuvre manuellement une à l'aide de sqlite3, mais je ne l'ai pas fait en aucune façon intelligente et avait-il l'air de chaque élément dans la base de données une à la fois... il était environ 300 fois plus lent.

Est la façon la plus intelligente de créer mon propre jeu de dicts, ne gardant qu'une mémoire à la fois, et la pagination dans certains de manière efficace?

Answer 1

Le module de poussée tiers mérite également d'être examiné. Il est très similaire à Shelve en ce sens qu'il s'agit d'un simple objet de type dict, mais il peut être stocké dans divers backends (tels que fichier, SVN et S3), fournit une compression facultative et est même threadsafe. C'est un module très pratique

 from shove import Shove

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

file_store['key'] = value
 

Answer 2

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

Answer 3

L' étagère module peut le faire; en tout cas, il doit être simple à tester. Au lieu de:

self.lengths = {}

faire:

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

Le seul hic, c'est que les clés de rayonnages doivent être des chaînes de caractères, de sorte que vous aurez à remplacer

self.lengths[indx]

avec

self.lengths[str(indx)]

(Je suis en supposant que vos clés sont juste des nombres entiers, comme par votre commentaire de Charles Duffy post)

Il n'y a pas de mise en cache dans la mémoire, mais votre système d'exploitation peut faire pour vous de toute façon.

[en fait, ce n'est pas tout à fait vrai: vous pouvez passer l'argument "d'écriture différée=True' sur la création. Le but de cela est de s'assurer de stocker les listes et d'autres mutable choses dans la tablette fonctionne correctement. Mais un effet secondaire est que l'ensemble du dictionnaire est mis en cache dans la mémoire. Depuis cela a causé des problèmes pour vous, c'est probablement pas une bonne idée :-) ]

Answer 4

La dernière fois que j'ai été confronté à un problème comme celui-ci, j'ai réécrit pour utiliser SQLite plutôt qu'un dict, et j'ai eu une augmentation considérable des performances. Cette augmentation des performances était au moins partiellement due aux capacités d'indexation de la base de données; en fonction de vos algorithmes, YMMV.

Un wrapper fin qui effectue des requêtes SQLite en __getitem__ et __setitem__ n'a pas beaucoup de code à écrire.

Answer 5

Avec un peu de réflexion, il semble que vous pourriez faire en sorte que le module d'étagère fasse ce que vous voulez.