python - 循环执行时间突然增加

Question

我有一个小软件，它用来计算每个三角形数字的因子数量，看看第一个因子数量超过X的三角形数字是什么（没错，这是一个Project Euler的问题，第12题，不过我还没解决它）……我在尝试把X设成一些随机值，看看代码的表现和运行时间时，发现了一些奇怪的现象（至少对我来说是这样）：当X=47时，执行时间的增加是很正常的，但当X=48时，执行时间的增加就不正常了，函数调用的次数也大大增加，简直是“爆炸”了……这是为什么呢？

代码如下：

def fac(n):
    c=0
    for i in range (1,n+1):
        if n%i==0:
            c=c+1
    return c

n=1

while True:
    summ=0
    for i in range (1,n+1):
        summ=summ+i
    if fac(summ)>X:
        break
    n=n+1

print summ

在进行性能分析时：

when X=45 :  314 function calls in 0.027 CPU seconds
when X=46 :  314 function calls in 0.026 CPU seconds
when X=47 :  314 function calls in 0.026 CPU seconds
when X=48 :  674 function calls in 0.233 CPU seconds
when X=49 :  674 function calls in 0.237 CPU seconds

我猜如果我继续测试下去，会发现其他地方系统调用的次数和时间也会突然增加，之前也有这样的情况，但因为时间太短，所以没什么影响……为什么函数调用会突然增加呢？难道不应该只是为新值多调用一次函数吗？

附注：我使用cProfile作为性能分析工具，这里的X只是为了演示，我直接在代码里写了这个值……提前谢谢你们……

Answer 1

如果你查看输出结果，会发现执行时间有几个突然增加的尖峰。

原因是需要的循环次数不是逐渐增加的，而是突然增加的。在你执行完 while True 循环后，打印出 n 的值，你就能看到这一点。

注意：Euler 是一个数学网站，不要写暴力破解的算法哦；)

Answer 2

你有没有看看实际涉及的数值呢？

第一个有超过47个因子的三角形数是 T(104) = 5460，它有48个因子。

但是，第一个有超过48个因子的三角形数是 T(224) = 25200，它有90个因子。所以说，计算起来要花更多的功夫也就不奇怪了。

如果你的代码运行到 T(n)，那么它会调用 range 2n 次和 fac n 次，总共会调用 3n 次函数。因此，对于 T(104)，需要312次函数调用，而对于 T(224)，需要672次函数调用。可以推测在某个地方还有2次额外的函数调用，这可能解释了你得到的性能分析结果。

---

你现在的策略可能无法解决 Project Euler 的问题。不过我可以给你一些提示。

• 每次计算三角形数时，你是否必须从 summ=0 开始重新计算？
• 你是否必须遍历所有数字直到 n 才能算出它有多少个因子？有没有更快的方法？（比如 2¹⁶ = 65536 有多少个因子？你真的需要从1遍历到65536吗？）
• 三角形数有多少个因子？（看看一些小的三角形数，看看能不能算出答案。）你能发现一些模式，帮助你计算更大三角形数的答案吗？