为什么我的方法使用查找表比暴力方法慢?

2024-03-28 08:38:58 发布

您现在位置:Python中文网/ 问答频道 /正文

这个问题是关于欧拉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()。在

^{2}$

那么我的代码中哪一部分一直占用着?在

我猜是两个if用字典键检查。在

但是由于我没有办法检查代码中的时间消耗(有没有呢?),我想听听你对此的看法。在


Tags: 代码innumberforiffoovaluenot
1条回答
网友
1楼 · 发布于 2024-03-28 08:38:58

时间消耗在字典键查找中,尤其是以下行:

if not number in d_value.keys():

以及

^{pr2}$

{e>只需调用一个简单的查找就可以了

if not number in d_value:

以及

if not d_value[number] in d_value:

现在您应该可以看到优化算法的更快性能。在

您可以通过在这个稍微重新组织的代码上使用cProfile模块来确定这一点:

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


def runit():
    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

import cProfile
cProfile.run('runit()')

输出

         51632 function calls in 2.366 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    2.366    2.366 <string>:1(<module>)
        1    1.711    1.711    2.366    2.366 ams.py:12(runit)
    10544    0.068    0.000    0.079    0.000 ams.py:3(d)
    10544    0.003    0.000    0.003    0.000 {math.sqrt}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
    19996    0.576    0.000    0.576    0.000 {method 'keys' of 'dict' objects}
    10545    0.008    0.000    0.008    0.000 {range}

这说明很多时间花在“dict”对象的“方法”keys上,即插入前字典查找。在

修改为仅使用value in d后,分析输出为:

         31636 function calls in 0.109 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.109    0.109 <string>:1(<module>)
        1    0.010    0.010    0.109    0.109 ams_fixed.py:12(runit)
    10544    0.088    0.000    0.099    0.000 ams_fixed.py:3(d)
    10544    0.002    0.000    0.002    0.000 {math.sqrt}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
    10545    0.009    0.000    0.009    0.000 {range}

相关问题 更多 >