这个问题是关于欧拉Problem 21:
基本算法是建立一个查找表d_value
,当我们从2
到{
然后为了尽可能少地调用d()
函数。在
无论何时我们有一个数字,我们都会检查这个数字是否已经存在于d_value.keys()
中。在
如果不是,那么我们将添加这个值为d(number)
的键。在
d_number
也是如此。在
然后我们比较它是否适合定义,如果适合,我们将number
添加到amicable_number_sum
。在
接下来number
。在
我的代码是这样的:
from math import sqrt
def d(number):
sum = 1
for foo in range(2, int(sqrt(number)) + 1):
if number % foo == 0:
sum += foo
sum += number/foo
return sum
d_value = {}
amicable_number_sum = 0
for number in range(2, 10000):
if not number in d_value.keys():
d_value[number] = d(number)
if not d_value[number] in d_value.keys():
d_value[d_value[number]] = d(d_value[number])
if number == d_value[d_value[number]] and not number == d_value[number]:
amicable_number_sum += number
print amicable_number_sum
这段代码需要2.14秒才能完成。在
还有一个我试图“避免”的暴力方法,它需要0.147秒才能完成。 :(
只要我们需要知道一个数的d()
,它就会调用函数d()
。在
那么我的代码中哪一部分一直占用着?在
我猜是两个if
用字典键检查。在
但是由于我没有办法检查代码中的时间消耗(有没有呢?),我想听听你对此的看法。在
时间消耗在字典键查找中,尤其是以下行:
以及
^{pr2}${e>只需调用一个简单的查找就可以了
以及
现在您应该可以看到优化算法的更快性能。在
您可以通过在这个稍微重新组织的代码上使用cProfile模块来确定这一点:
输出:
这说明很多时间花在“dict”对象的“方法”keys上,即插入前字典查找。在
修改为仅使用
value in d
后,分析输出为:相关问题 更多 >
编程相关推荐