Что такое хорошая реализация набора на диске для Python?

Я работаю над программой на Python, которой необходимо хранить постоянную структуру данных «набор», содержащую множество хэш-значений фиксированного размера (SHA256, но это не важно). Важнейшими операциями являются вставка и поиск. Удаление не требуется для обычной работы. Набор будет расти со временем и в конечном итоге может не все поместиться в памяти.

Я рассмотрел:

  • set, хранящийся на диске с использованием pickle (медленно [несколько секунд] для записи нового файла на диск, в конечном итоге не помещается в память)
  • база данных SQLite (дополнительная зависимость недоступна по умолчанию)
  • настраиваемая сбалансированная древовидная структура на основе диска, такая как B-дерево или аналогичная

В идеале должен быть встроенный модуль Python, обеспечивающий поддержку этих операций. Какой здесь хороший вариант?

После того, как я составил это, я нашел Fast disk-based hashtables?, у которого есть несколько хороших идей. Мне нравится принятый там ответ mmap/bucket.

(Это для перезаписи shaback, если вам интересно.)


python set data-structures
person Greg Hewgill    schedule 19.05.2011    source источник
comment
На самом деле реализация mmap/bucket — это именно то, что мне нужно. В отсутствие лучших идей я закодирую его и опубликую здесь.   -  person Greg Hewgill    schedule 19.05.2011
comment
Ради интереса, каков порядок величины того, сколько значений вам может понадобиться хранить?   -  person NPE    schedule 19.05.2011
comment
@aix: это для программы резервного копирования, по одному хэшу на файл. Сколько файлов в файловой системе? :)   -  person Greg Hewgill    schedule 19.05.2011

Ответы (4)


arrow_upward
4
arrow_downward

Другой вариант — использовать shelve, я знаю, что это то же самое, что и рассол (под капотом) но я думаю, что это хороший вариант (которого я не видел в вашем списке вариантов :-)) или, может быть, если вы не возражаете против использования сторонней библиотеки, вы можете взглянуть на пушить (это как полка++).

person mouad    schedule 19.05.2011
comment
Это выглядит как хороший вариант, приятно, как он выбирает подходящий сервер на основе того, что доступно. - person Greg Hewgill; 19.05.2011

arrow_upward
0
arrow_downward

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

person lassej    schedule 19.05.2011
comment
SQLite не всегда доступен по умолчанию в установках Python. - person Greg Hewgill; 19.05.2011
comment
@Greg: это в Python 2.5 и выше; этого недостаточно? - person Katriel; 19.05.2011
comment
@katriealex: Это как бы там, потому что части Python установлены по умолчанию. Но, по крайней мере, во FreeBSD установка .so требует дополнительного шага. - person Greg Hewgill; 19.05.2011

arrow_upward
0
arrow_downward

Вы можете использовать базу данных в стиле DBM. Я делаю то же самое с dbm, просто сохраняя все ключи со значением «1». Поскольку это BSD, модуль dbhash должен работать. (он устарел, поэтому нет Python 3, и из-за этого не очень хорошая идея для долгосрочного использования). В противном случае используйте модули gdbm (dbm.gdbm в Python 3) и ndbm(dbm.dbm в Python 3). Также есть модуль dumpdbm (dbm.dumbdbm в Python 3), который является чистым питоном и всегда работает, но немного медленнее. Кроме того, если вы собираетесь иметь несколько одновременных операций чтения и записи, однозначно не используйте модуль dumpdbm.

Все различные модули dbm работают так же, как словарь Python, за исключением того, что ключи и значения должны быть строками. Вы можете использовать ключевое слово «in» так же, как для набора или словаря.

person Brian Minton    schedule 02.08.2012

arrow_upward
0
arrow_downward

Dbm и установка второго значения как произвольного значения 1, как предложил Брайан Минтон, является удобным решением. cPickle тоже хорош

Однако вам также следует рассмотреть возможность использования json. Проверьте Google, но, насколько мне известно, парсер json работает быстрее, чем Pickle/cPickle. (например, http://kovshenin.com/2010/pickle-vs-json-what-is-faster/)

person ThinkBonobo    schedule 22.01.2014