Оптимизация функции разбиения

Question

Вот код, в 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)). Я хочу спросить вас, могу ли я оптимизировать свой код или намекнуть на другой, но более быстрый алгоритм или подход. Любые предложения по оптимизации приветствуются.

И нет, прежде чем вы спросите, это не для домашней работы или проекта Эйлера, а для значения опыта.

Answer 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)

IЯ написал их так, чтобы я не вводил вычисления с плавающей точкой - для больших n использование чисел с плавающей запятой приведет к ошибкам (сравните результаты для n = 100000001).

Вы можете использовать timeit *Модуль 1010 * для тестирования небольших фрагментов кода.Когда я протестировал все пятиугольные функции (вашу и мою), результаты для моей были быстрее.Ниже приведен пример, который проверяет вашу функцию 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, а другой для обновления total.Я сохраняю результат в переменной, поэтому вычисление выполняется только один раз за цикл.

Используя модуль 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», чтобы увидеть, что вы можете найти.

Наконец, одна из ссылок в нижней части страницы википедии, которую вы упомянули, представляет собой академическую статью о быстрых алгоритмахдля расчета номеров разделов.Быстрый взгляд показывает, что он содержит псевдокод для алгоритмов.Эти алгоритмы, вероятно, будут быстрее, чем все, что вы или я могли бы создать.