以下是一些评论。请注意,我不是这方面的专家,因为我也喜欢搞数学(和欧拉计划)。
我重新定义了五边形数函数如下:
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 http://docs.python.org/library/timeit.html#module-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 http://docs.python.org/library/profile.html#module-profilemodule(对于 python >= 2.5,否则为 profile 模块),您可以看到代码大部分时间都花在哪里。这是一个基于您的配分函数的示例。
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
and round
内置函数。我已经将五边形函数的调用次数几乎减少了一半(gen_pent_new
and pent_new
)
可能还有其他技巧可以提高 python 代码的速度。我会在这里搜索“python optimization”,看看你能找到什么。
最后,您提到的维基百科页面底部的链接之一是学术论文 http://www.site.uottawa.ca/~ivan/F49-int-part.pdf计算分区数的快速算法。快速浏览一下就会发现它包含算法的伪代码。这些算法可能比你我能产生的任何算法都要快。