优化分区功能 [英] Optimizing a Partition Function
问题描述
这是python中的代码:
Here is the code, in 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
它使用这种方法来计算分区:
It uses this method to calculate partitions:
p(k) = p(k − 1) + p(k − 2) − p(k − 5) − p(k − 7) + p(k − 12) + p(k − 15) ...
(来源:维基百科)
但是，当涉及到大数时(超过p(10 ^ 3))，该代码将花费相当长的时间.我想问你是否可以优化我的代码，或者提示我使用其他但更快的算法或方法.欢迎任何优化建议.
However, the code is taking quite some time when it comes to large numbers (over p(10^3)). I want to ask you if I can optimize my code, or hint me to a different but faster algorithm or approach. Any optimization suggestions are welcome.
不，在您问之前，这不是为了家庭作业或欧拉计划，而是出于经验价值.
推荐答案
以下是一些注释.请注意，我也不是这方面的专家，因为我也很喜欢弄乱数学(和欧拉计划).
Here are some comments. Note that I am no expert on this stuff, by I too like messing about with maths (and Project Euler).
我重新定义了五角形数函数，如下所示:
I have redefined the pentagonal number functions as follows:
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的结果).
I have written them in such a way that I don't introduce floating point calculations - for large n using floats will introduce errors (compare the results for n = 100000001).
您可以使用 timeit 模块测试以下内容的小片段代码.当我测试所有五边形函数(您和我的)时，我的结果更快.以下是测试您的gen_pent函数的示例.
You can use the timeit module to test small snippets of code. When I tested all pentagonal functions (yours and mine), the results for mine were quicker. The following is an example which tests your gen_pent function.
# 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函数要快.但是，这可能是由于对五角数函数进行了改进.
Here is a slight modification of your partition function. Again, testing with timeit shows that it is faster than your partition function. However, this may be due to the improvements made to the pentagonal number functions.
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下进行更新.我将结果存储在变量中，因此每个循环只进行一次计算.
In your partition function, you calculate the general pentagonal number twice for each loop. Once to test in the while condition, and the other to update total. I store the result in a variable, so only make the calculation once per loop.
使用 cProfile 模块(对于python> = 2.5，否则为个人资料模块)，您可以看到代码大部分时间都花在了哪里.这是一个基于您的分区功能的示例.
Using the cProfile module (for python >= 2.5, otherwise the profile module) you can see where your code spends most of its time. Here is an example based on your partition function.
import cProfile
import pstats
cProfile.run('partition(70)', 'partition.test')
p = pstats.Stats('partition.test')
p.sort_stats('name')
p.print_stats()
这将在控制台窗口中产生以下输出:
This produced the following output in the console window:
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)
现在分析我的分区功能:
Now profiling my partition function:
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)的调用次数几乎减少了一半
You can see in my results there are no calls to the len and round builtin functions. And I have nearly halved the number of calls to the pentagonal functions (gen_pent_new and pent_new)
可能还有其他技巧可以提高python代码的速度.我会在这里搜索"python优化"以查看您可以找到的内容.
There are probably other tricks to improving the speed of python code. I would search here for 'python optimization' to see what you can find.
Finally, one of the links at the bottom of the wikipedia page you mentioned is an academic paper on fast algorithms for calculating partition numbers. A quick glance shows it contains pseudocode for the algorithms. These algorithms will probably be faster than anything you or I could produce.
这篇关于优化分区功能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
