优化分区功能

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)

我已经用这样的方式编写它们,我没有引入浮点计算 - 对于大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条件下进行测试,另一个进行更新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 optimization'来查看你能找到的东西.

最后,您提到的维基百科页面底部的一个链接是关于计算分区数的快速算法的学术论文.快速浏览显示它包含算法的伪代码.这些算法可能比您或我可以生成的任何算法都快.