为什么除数的一个函数比另一个快 >3000%？

Question

我在 https://www.practicepython.org/ when I did this task https://www.practicepython.org/exercise/2014/02/26/04-divisors.html 上做了一些简单的 Python 练习。

我想测试不同的答案编码方式，我在评论区看到的解决方案激起了我的兴趣；两个代码看起来很相似，但一个比另一个快将近 4000%！

代码：

import time

start = time.time()

print("Fast code:")

#the slow code
def divisor(x):
    divisors = []
    for i in range(1, int(x)):
        if x % i == 0:
            divisors.append(i)
            divisors.sort()
    print(divisors)


divisor(50000000)
end = time.time()
print("Time elapsed: ")
print(end - start)

print("Fast code:")

start = time.time()

#the fast code!
def divisor2(x):
    divisors = []
    for i in range(1, int(x**.5)):
        if x % i == 0:
            divisors.append(i)
            divisors.append(x//i)
            divisors.sort()
    print(divisors)
divisor2(50000000)
end = time.time()
print("Time elapsed: ")
print(end - start)

已用时间（慢码）：

3.1739981174468994

已用时间（快码）：

0.0010004043579101562

任何人都可以告诉我这是怎么可能的，这样也许任何人都可以为他们的工具带带回家一些宝贵的快速编码技能吗？

Answer 1

x**.5是x的1/2次方，是平方根。

两者都使用 x = 50,000,000，第一个使用：

for i in range(1, int(x)):

五千万个循环.

第二个：

for i in range(1, int(x**.5)):

七千个循环.

计算除数时可以这样做的原因是因为它们形成了矩形的两侧：

 __
|  |
|  |
|__|

如果你知道面积（目标，5000万），并且你知道一侧（计数器i），那么你可以计算出另一侧。两边相同的地方就是平方根，它的作用就像一个支点，如果一个比它短，那么另一个必须更长，并平衡它。也就是说，100/2 = 50 给你 2 和 50。

所以你可以数到平方根来找到所有的简短答案，计算出每一个的另一边（平衡），然后你就有了所有的答案。 100/10 = 10 给你 10 作为除数，并告诉你如果你一直数到 100/50 = 2 你已经从另一边看到它并得到 50.

这就是为什么第二个代码有：

        divisors.append(i)
        divisors.append(x//i)

在仅测试一个值后向列表中添加两个值。

Answer 2

经典 O(n) 与 O(n^0.5)

第一个正在执行 50000000 次操作

第二个正在执行 7000 次操作（减少 7000 次）

时差呢？快3000倍？有些东西没有加起来。

这里！

divisors.sort()

您在找到每个除数对后执行此操作，这是一项昂贵的操作。只需将其向左移动 2 个缩进级别（与 print 相同的级别），即可看到约 7000 倍或更多的性能提升。

为什么会这样？

好吧，如果你发现 15 可以被 3 整除，那么为什么要检查每隔一个数字然后再次检查 5，当你知道如果 15 可以被 3 整除，它也可以被 15/3 整除。也没有数字可以被任何大于其平方根的数字整除，结果也大于平方根。因此，运行循环这么长时间是没有意义的——它不会找到任何解决方案。由于 50000000 绝对不能被任何大于 7071.067811865475 的数字整除，这将导致另一个大于 7071.067811865475 的数字，如果我们将找到的每个除数的除法结果相加，检查 7072 和更大的数字会浪费大量时间。

为什么除数的一个函数比另一个快 >3000%？

Why is one function of divisor >3000% faster than the other?

python

performance

time

function