Словарь на основе диска Python

Question

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

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

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

Answer 1

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

Answer 2

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

from shove import Shove

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

file_store['key'] = value

Answer 3

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

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

Answer 4

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

self.lengths = {}

делай:

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

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

self.lengths[indx]

с

self.lengths[str(indx)]

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

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

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

Answer 5

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

Answer 6

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

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

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

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

Answer 7

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

Answer 8

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

Answer 9

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