Оптимизация функции раздела
Вот код в Python:
# function for pentagonal numbers
def pent (n): return int((0.5*n)*((3*n)-1))
# function for generalized pentagonal numbers
def gen_pent (n): return pent(int(((-1)**(n+1))*(round((n+1)/2))))
# array for storing partitions - first ten already stored
partitions = [1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42]
# function to generate partitions
def partition (k):
if (k < len(partitions)): return partitions[k]
total, sign, i = 0, 1, 1
while (k - gen_pent(i)) >= 0:
sign = (-1)**(int((i-1)/2))
total += sign*(partition(k - gen_pent(i)))
i += 1
partitions.insert(k,total)
return total
Это использует этот метод для вычисления разделов:
p(k) = p(k − 1) + p(k − 2) − p(k − 5) − p(k − 7) + p(k − 12) + p(k − 15) ...
(источник: Википедия)
Однако код занимает некоторое время когда дело доходит до больших количеств (по p (10^3)). Я хочу спросить Вас, если я могу оптимизировать свой код, или подсказывать меня другому, но более быстрому алгоритму или подходу. Любые предложения оптимизации приветствуются.
И не перед выяснением это не для домашней работы или Euler Проекта, для значения опыта.
1 ответ
Вот несколько комментариев. Обратите внимание, что я не являюсь экспертом в этом вопросе, потому что мне тоже нравится возиться с математикой (и Project Euler).
Я переопределил функции пятиугольных чисел следующим образом:
def pent_new(n):
return (n*(3*n - 1))/2
def gen_pent_new(n):
if n%2:
i = (n + 1)/2
else:
i = -n/2
return pent_new(i)
Я написал их таким образом, что я не использую вычисления с плавающей запятой - для больших n использование чисел с плавающей запятой приведет к ошибкам (сравните результаты для n = 100000001 ).
Вы можете использовать модуль timeit для тестирования небольших фрагментов кода. Когда я протестировал все пятиугольные функции (вашу и мою), результаты для моей были быстрее. Ниже приведен пример проверки вашей функции gen_pent .
# Add this code to your script
t = Timer("for i in xrange(1, 100): gen_pent(i)", "from __main__ import gen_pent")
print t.timeit()
Вот небольшая модификация вашей функции partition . Опять же, тестирование с timeit показывает, что это быстрее, чем ваша функция partition . Однако это может быть связано с улучшениями, внесенными в функции пятиугольного числа.
def partition_new(n):
try:
return partitions_new[n]
except IndexError:
total, sign, i = 0, 1, 1
k = gen_pent_new(i)
while n - k >= 0:
total += sign*partition_new(n - k)
i += 1
if i%2: sign *= -1
k = gen_pent_new(i)
partitions_new.insert(n, total)
return total
В вашей функции распределения вы вычисляете общее пятиугольное число дважды для каждого цикла. Один раз для проверки в условии while, а другой - для обновления итого . Я сохраняю результат в переменной, поэтому выполняю расчет только один раз за цикл.
Используя модуль cProfile (для python> = 2.5, в противном случае - модуль профиля), вы можете увидеть, на что ваш код тратит большую часть своего времени.Вот пример, основанный на вашей функции разделения.
import cProfile
import pstats
cProfile.run('partition(70)', 'partition.test')
p = pstats.Stats('partition.test')
p.sort_stats('name')
p.print_stats()
Это произвело следующий вывод в окне консоли:
C:\Documents and Settings\ags97128\Desktop>test.py
Fri Jul 02 12:42:15 2010 partition.test
4652 function calls (4101 primitive calls) in 0.015 CPU seconds
Ordered by: function name
ncalls tottime percall cumtime percall filename:lineno(function)
552 0.001 0.000 0.001 0.000 {len}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
60 0.000 0.000 0.000 0.000 {method 'insert' of 'list' objects}
1 0.000 0.000 0.015 0.015 <string>:1(<module>)
1162 0.002 0.000 0.002 0.000 {round}
1162 0.006 0.000 0.009 0.000 C:\Documents and Settings\ags97128\Desktop\test.py:11(gen_pent)
552/1 0.005 0.000 0.015 0.015 C:\Documents and Settings\ags97128\Desktop\test.py:26(partition)
1162 0.002 0.000 0.002 0.000 C:\Documents and Settings\ags97128\Desktop\test.py:5(pent)
Теперь профилируем мою функцию разделения:
Fri Jul 02 12:50:10 2010 partition.test
1836 function calls (1285 primitive calls) in 0.006 CPU seconds
Ordered by: function name
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
60 0.000 0.000 0.000 0.000 {method 'insert' of 'list' objects}
1 0.000 0.000 0.006 0.006 <string>:1(<module>)
611 0.002 0.000 0.003 0.000 C:\Documents and Settings\ags97128\Desktop\test.py:14(gen_pent_new)
552/1 0.003 0.000 0.006 0.006 C:\Documents and Settings\ags97128\Desktop\test.py:40(partition_new)
611 0.001 0.000 0.001 0.000 C:\Documents and Settings\ags97128\Desktop\test.py:8(pent_new)
Вы можете видеть в моих результатах, что нет вызовов len и round встроенные функции. И я почти вдвое сократил количество вызовов пятиугольных функций ( gen_pent_new и pent_new )
Вероятно, есть и другие уловки для повышения скорости кода Python. Я бы поискал здесь «оптимизация Python», чтобы узнать, что вы можете найти.
Наконец, одна из ссылок внизу страницы википедии, которую вы упомянули, - это академическая статья о быстрых алгоритмах вычисления количества разделов. Беглый взгляд показывает, что он содержит псевдокод для алгоритмов. Эти алгоритмы, вероятно, будут быстрее, чем все, что вы или я могли бы создать.