Хранение огромной хеш-таблицы в файле на Python

Question

Эй. У меня есть функция, которую я хочу запомнить, однако она имеет слишком много возможных значений. Есть ли удобный способ сохранить значения в текстовом файле и сделать его читаемым из них? Например, что-то вроде хранения предварительно вычисленного списка простых чисел до 10 ^ 9 в текстовом файле? Я знаю, что это медленно читать из текстового файла, но нет другого варианта, если объем данных действительно огромен. Спасибо!

Answer 1

Для списка простых чисел до 10**9 зачем вам хеш? Какими будут КЛЮЧИ ?! Звучит как прекрасная возможность для простого, простого двоичного файла! По теореме простого числа таких простых чисел около 10**9/ln(10**9) - т.е. 50 миллионов или чуть меньше. При 4 байтах на простое число, это только 200 МБ или меньше - идеально подходит для array.array("L") и его методов, таких как fromfile и т. Д. (См. документы ). Во многих случаях вы можете фактически высосать все 200 МБ в память, но, в худшем случае, вы можете получить их часть (например, с помощью mmap и fromstring метода array.array), сделав бинарный поиск там (например, через bisect ) и т. д. и т. д.

Когда вам НУЖНО огромное огромное хранилище значений ключей - гигабайты, а не мизерные 200 МБ! -) - я обычно рекомендовал shelve, но после неприятного реального жизненного опыта с огромными полками (производительность, надежность и т. д.), в настоящее время я рекомендую вместо этого ядро ​​базы данных - sqlite хорош и поставляется с Python, PostgreSQL еще лучше, нереляционные, такие как CouchDB, могут быть еще лучше и т. д.

Answer 2

Вы можете использовать модуль полки для сохранения словоподобной структуры в файле. Из документации Python:

import shelve

d = shelve.open(filename) # open -- file may get suffix added by low-level
                          # library

d[key] = data   # store data at key (overwrites old data if
                # using an existing key)
data = d[key]   # retrieve a COPY of data at key (raise KeyError if no
                # such key)
del d[key]      # delete data stored at key (raises KeyError
                # if no such key)
flag = d.has_key(key)   # true if the key exists
klist = d.keys() # a list of all existing keys (slow!)

# as d was opened WITHOUT writeback=True, beware:
d['xx'] = range(4)  # this works as expected, but...
d['xx'].append(5)   # *this doesn't!* -- d['xx'] is STILL range(4)!

# having opened d without writeback=True, you need to code carefully:
temp = d['xx']      # extracts the copy
temp.append(5)      # mutates the copy
d['xx'] = temp      # stores the copy right back, to persist it

# or, d=shelve.open(filename,writeback=True) would let you just code
# d['xx'].append(5) and have it work as expected, BUT it would also
# consume more memory and make the d.close() operation slower.

d.close()       # close it

Answer 3

Вы также можете просто использовать предельную грубую силу и создать файл Python, содержащий всего одну инструкцию:

seedprimes = [3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,
79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173, ...

, а затем просто импортируйте его. (Вот файл с простыми числами до 1e5: http://python.pastebin.com/f177ec30).

from primes_up_to_1e9 import seedprimes

Answer 4

Простое наложение хеш-таблицы на диск приведет к потере производительности примерно на 5 порядков по сравнению с реализацией в памяти (или, по крайней мере, 3, если у вас SSD). Имея дело с жесткими дисками, вы захотите извлечь все биты локальности данных и кэширования, которые вы можете получить.

Правильный выбор будет зависеть от деталей вашего варианта использования. Сколько производительности вам нужно? Какие операции вам нужны для структуры данных? Вам нужно только проверить, содержит ли таблица ключ, или вам нужно получить значение, основанное на ключе? Можете ли вы предварительно вычислить таблицу или вам нужно будет изменить ее на лету? Какой уровень хитов вы ожидаете? Можете ли вы отфильтровать значительное количество операций, используя фильтр Блума? Распределены ли запросы равномерно или вы ожидаете какую-то временную локализацию? Можете ли вы заранее предсказать кластеры населенных пунктов?

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

Answer 5

Для Project Euler я сохранил предварительно вычисленный список простых чисел до 10 ** 8 в текстовом файле, просто записав их в формате через запятую. Это хорошо работало для этого размера, но не слишком хорошо для увеличения.

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

Answer 6

Посмотрим, где находится узкое место. Когда вы собираетесь читать файл, жесткий диск должен вращаться достаточно, чтобы иметь возможность читать с него; затем он читает большой блок и кэширует результаты.

Итак, вам нужен какой-то метод, который будет точно угадывать какую позицию в файле вы будете читать из , а затем делать это ровно один раз. Я почти уверен, что стандартные модули БД подойдут вам, но вы можете сделать это сами - просто откройте файл в двоичном режиме для чтения / записи и сохраните ваши значения, скажем, в 30 цифр (= 100 бит) 13-байтовые) числа.

Затем используйте стандартные file методы.

Answer 7

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