Я пишу скрипт Python 3.4, который выполняет для меня большие вычисления. Этот расчет включает в себя вычисление много-много биномиальных коэффициентов и использование каждого из них. много раз в суммах и умножениях с другими числами. Каждый раз, когда для расчета требуется bc (биномиальный коэффициент), он проверяет, был ли уже рассчитан bc. Если это так, он возвращает это уже рассчитанное значение. В противном случае он вычисляет его и сохраняет для последующего поиска. В настоящее время моя функция bc(n,k), которая вычисляет bc "n, выбирает k", выглядит следующим образом:
bcvalues = {}
def bc(n,k):
k = min(k,n-k) # take advantage of symmetry
if (n,k) in bcvalues: # check whether value has already been calculated
return bcvalues[(n,k)] # if so, return that already calculated value
if k == 0 or n <= 1: # base case
return 1
result = bc(n-1,k) + bc(n-1,k-1) # Use formula for Pascal's triangle
bcvalues[(n,k)] = result # store the value for later look-up
return result
Моя справочная таблица представляет собой словарь с кортежем (n,k) в качестве ключа и bc(n,k) в качестве значения. Он удовлетворяет всем
Строгие требования
- Может быть заполнен/расширен до произвольного размера во время выполнения (до запуска расчета я понятия не имею, сколько bc нужно вычислить, но это много bc)
- Значения могут быть сколь угодно большими (либо
int(тип Python 3), либо тип gmpy2mpz, Я еще не уверен). Это важно, так как значения могут стать очень большими. - Его можно проиндексировать двумя натуральными числами n и k
- Bc для некоторых кортежей (n,k) можно пропустить (например, может быть запись для (100,50), но нет записи для (100,49))
Однако я не уверен, является ли это оптимальным решением (если оно вообще существует) с точки зрения
Требования к производительности (в порядке важности)
- Быстрый просмотр/считывание
- Низкое потребление памяти (в тестах мой словарь уже занимал несколько ГБ; в конечном итоге я могу арендовать вычислительную мощность на машинах с большой памятью)
- Быстрая запись в справочную таблицу
В тестах с очень небольшим размером входных данных, которые я только что провел, функция bc была вызвана 16 миллионов раз, и это число, вероятно, сильно возрастет для размеров входных данных, которые меня действительно интересуют. Следовательно, производительность имеет значение.
Мое текущее решение (словарь) имеет то преимущество, что в конце прогона вычислений я могу сериализовать справочную таблицу (используя рассол), так что, когда я выполняю новый прогон с более высокими входными значениями, я могу распаковать его и иметь все имеющиеся БК, которые были рассчитаны в предыдущих прогонах. Это сильный бонус:
Бонусный балл
- Справочную таблицу можно легко сериализовать.
Мой вопрос
Что, кроме словаря, может быть кандидатом на соответствие этим критериям?
Я подумал о написании функции, которая биективно сопоставляет кортежи (n,k) треугольника с натуральными числами, а затем использует список для справочной таблицы. Насколько это перспективно? Другие идеи?
