Python Sur Disque Dictionnaire

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?

InformationsquelleAutor Claudiu | 2008-10-22
  1. 22

    De hachage-sur-disque est généralement traitée avec Berkeley DB ou quelque chose de semblable, plusieurs options sont répertoriées dans le Python la Persistance des Données, la documentation. Vous pouvez avant avec un cache en mémoire, mais je préfère tester des performances natives d'abord; avec système d'exploitation de la mise en cache en place, il pourrait arriver la même.

    InformationsquelleAutor Parand
  2. 55

    La 3ème partie pousser module est également la peine de prendre un coup d'oeil. Il est très similaire, la mise à l'écart en ce qu'il est un simple dict-comme l'objet, mais il peut stocker à différents backends (tels que fichier, SVN, et S3), fournit une option de compression, et est même thread-safe. C'est un module très pratique

    from shove import Shove

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

file_store['key'] = value
    • Cela mérite plus d'attention qu'elle reçoit. Il peut également être utilisé avec SQLite si vous ne souhaitez pas utiliser un serveur distinct, ou Berkeley DB, si vous ne voulez pas utiliser SQLite.
    • Oui, j'ai longtemps chercher ce genre de module. Plan pour ajouter redis depuis que ce qu'on utilise pour le kv magasin.
    InformationsquelleAutor Matthew Trevor
  3. 7

    Dernière fois que j'étais face à un problème comme celui-ci, je l'ai réécrit pour l'utilisation de SQLite, plutôt que d'un dict, et a eu une énorme augmentation de la performance. Cette augmentation de la performance a été au moins partiellement sur le compte de la base de données d'indexation de l'capacités; en fonction de vos algorithmes, YMMV.

    Un wrapper mince qui ne SQLite requêtes dans __getitem__ et __setitem__ n'est pas la quantité de code à écrire.

    • Souhaitez-vous exactement comment utiliser sqlite de l'indexation? je l'ai fait ici est de créer un tableau comme ceci: "cur.execute('create table vals-les-bains (indx ENTIER, chainlen INTEGER)')", puis j'ai "cur.execute('SELECT * from vals-les-bains où indx=%d' % i)" pour une recherche.
    • créer une table de vals (indx INTEGER PRIMARY KEY, chainlen ENTIER)
    • mon programme était telle que j'ai pu mettre en œuvre une certaine logique dans la couche de base de données, donc je pourrais laisser le DB ne de filtrage et de tel; il était plus que juste un idiot magasin.
    • Vous pouvez également utiliser une taille de cache pragma dire sqlite à utiliser plus de mémoire pour le cache: sqlite.org/pragma.html
    • le chemin, la pratique, vous êtes à l'aide de là-bas (à l'aide de % de remplacer des valeurs dans vos instructions SQL via la mise en forme de chaîne) est fondamentalement précaire; ce n'est pas une grosse affaire pour les décimales, mais si vous le faites pour les chaînes qu'il laisse, vous vous ouvrez à des attaques par injection SQL. cur.execute('SELECT * from vals where indx=?', (i,)) est plus sûr, et peut également exécuter plus rapidement lorsqu'il est invoqué à plusieurs reprises en raison de l'sqlite module de mise en cache des requêtes préparées.
    • oui, vous avez raison. je fais généralement ce que vous suggérez, mais merci de le signaler. n'a jamais fait mal à ce point conduit à la maison plus de personnes.

    InformationsquelleAutor Charles Duffy
  4. 7

    La é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 🙂 ]

    • en fait, j'ai essayé cela, mais il était bien trop lent.. je pense que j'ai besoin d'une sorte de manuel de la solution de pagination pour obtenir toute vitesse raisonnable.
    InformationsquelleAutor John Fouhy
  5. 2

    Avec un peu de réflexion, il semble que vous pourriez obtenir de l' étagère module à faire ce que vous voulez.

    InformationsquelleAutor Dustin Wyatt
  6. 2

    J'ai lu que vous pensez mettre en veilleuse est trop lent et vous avez essayé de pirater votre propre dict utilisation de sqlite.

    Un autre fait: le

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

    Il semble assez efficace (et sebsauvage est un très bon codeur). Vous pourriez peut-être lui donner un essai ?

    InformationsquelleAutor e-satis
  8. 0

    Vous devez apporter de plus qu'un élément à la fois s'il y a une heuristique de savoir qui sont les plus susceptibles éléments à extraire prochaine, et n'oubliez pas l'index comme Charles mentionne.

    InformationsquelleAutor Vinko Vrsalovic
  9. 0

    Pour des cas d'utilisation simples sqlitedict
    peut vous aider. Toutefois, lorsque vous avez beaucoup plus de bases de données complexes, vous peut éventuellement essayer l'un des plus upvoted réponses.

    InformationsquelleAutor Raymond Peng