优化分区函数

下面是代码，在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) ...

（来源：Wikipedia）

但是，代码当涉及到大量数据时（p（10^3）），需要相当长的时间。我想问你是否可以优化我的代码，或者提示我采用不同但更快的算法或方法。欢迎任何优化建议。

不，我可以告诉大家，这不是家庭作业或项目欧拉，其经验值。

来源

2010-07-02 Khaled

这里有一些意见。请注意，我并不是这方面的专家，我也喜欢用数学（和欧拉项目）搞乱。

我已经重新定义了五角数功能如下：

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 = 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没有呼叫和内建函数。我几乎减半了五角函数的调用次数（gen_pent_new和pent_new）

提高python代码的速度可能还有其他技巧。我会在这里搜索'python优化'，看看你能找到什么。

最后，您提到的维基百科页面底部的链接之一是用于计算分区号的快速算法的academic paper。快速浏览显示它包含算法的伪代码。这些算法可能比我们能够生成的任何东西都快。

来源

2010-07-02 12:00:56

优化分区函数

回答

相关问题