Python дисковый словарь

Question

Я выполнял некоторый динамический программный код (пытаясь опровергнуть гипотезу Коллатца = P), и я использовал dict для хранения длин цепей, которые я уже вычислил. Очевидно, что в какой-то момент не хватило памяти. Есть ли какой-нибудь простой способ использовать какой-либо вариант dict, который будет выводить части себя на диск, когда ему не хватит места? Очевидно, что это будет медленнее, чем диктовка в памяти, и, вероятно, в конечном итоге это займет мое место на жестком диске, но это может относиться к другим проблемам, которые не так бесполезны.

Я понял, что дисковый словарь в значительной степени является базой данных, поэтому я вручную реализовал его, используя sqlite3, но я не делал этого каким-либо умным способом и заставлял искать каждый элемент в БД по одному ... это было примерно в 300 раз медленнее.

Является ли самый умный способ просто создать мой собственный набор диктов, сохраняя только один в памяти за раз, и каким-то эффективным образом выкладывать их на страницы?

Answer 1

Также стоит взглянуть на сторонний модуль shove . Он очень похож на shelve в том, что это простой объект, похожий на dict, однако он может храниться в различных бэкэндах (таких как file, SVN и S3), обеспечивает дополнительное сжатие и даже безопасен для потоков. Это очень удобный модуль

from shove import Shove

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

file_store['key'] = value

Answer 2

Хэш-на-диске, как правило, решается с помощью Berkeley DB или чего-то подобного - несколько параметров перечислены в документации Python Data Persistence . Вы можете обработать его с помощью кеша в памяти, но сначала я проверю нативную производительность; с кэшированием операционной системы может получиться примерно то же самое.

Answer 3

Модуль полка может сделать это; во всяком случае, это должно быть просто проверить. Вместо:

self.lengths = {}

сделать:

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

Единственная загвоздка в том, что ключи от полок должны быть струнами, поэтому вам придется заменить

self.lengths[indx]

с

self.lengths[str(indx)]

(я предполагаю, что ваши ключи - просто целые числа, согласно вашему комментарию к сообщению Чарльза Даффи)

В памяти нет встроенного кэширования, но ваша операционная система может сделать это за вас.

[на самом деле, это не совсем так: вы можете передать аргумент writeback = True при создании. Цель этого - убедиться, что хранение списков и других изменяемых вещей на полке работает правильно. Но побочным эффектом является то, что весь словарь кэшируется в памяти. Так как это вызвало проблемы для вас, это, вероятно, не очень хорошая идея :-)]

Answer 4

В прошлый раз, когда я столкнулся с такой проблемой, я переписал использовать SQLite, а не dict, и у меня было значительное увеличение производительности. Это повышение производительности было, по крайней мере, частично благодаря возможностям индексирования базы данных; в зависимости от ваших алгоритмов, YMMV.

Тонкая оболочка, которая выполняет запросы SQLite в __getitem__ и __setitem__, не так много кода для записи.

Answer 5

Я читал, что вы думаете, что полка слишком медленная, и вы пытались взломать свой собственный диктат с помощью sqlite.

Другой тоже сделал это:

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

Это кажется довольно эффективным (и sebsauvage - довольно хороший кодер). Может быть, вы могли бы попробовать?

Answer 6

Немного подумав, кажется, что вы можете заставить модуль полки делать то, что вы хотите.

Answer 7

прочитайте ответ на этот вопрос от GvR;) Сортировка миллиона 32-разрядных целых чисел в 2 МБ ОЗУ с использованием Python

Answer 8

Я еще не пробовал, но Hamster DB перспективен и имеет интерфейс Python.

Answer 9

Вы должны приносить более одного элемента за раз, если есть какая-то эвристика, чтобы знать, какие из них наиболее вероятны для получения следующей, и не забывайте индексы, как упоминает Чарльз.