为什么python的for循环对于大输入如此非线性？

Question

我正在对一些python代码进行基准测试,我注意到了一些奇怪 我使用以下函数来测量迭代空for循环所需的速度:

def f(n):
    t1 = time.time()
    for i in range(n):
        pass
    print(time.time() - t1)

f(10**6)打印about 0.035,f(10**7)about 0.35,f(10**8)about 3.5和f(10**9)about 35.但是f(10**10)？好吧2000.这当然是意料之外的.为什么迭代10倍的元素需要花费60倍的时间？什么是python的for循环导致这个？这是特定于python的,还是会出现在很多语言中？

Answer 1

当你达到目标时,10^9你会超出32位整数范围.Python3然后透明地将你移动到任意精度整数,这些整数分配和使用要慢得多.

一般来说,使用如此大的数字是Python3比Python2慢得多的领域之一(至少在许多系统上都有快速的64位整数).好的一面是它使python更容易使用,溢出类型错误更少.

Answer 2

一些准确的时间使用timeit显示时间实际上大致增加与输入大小一致,所以你的时间似乎有很长的路要走:

In [2]: for n in [10**6,10**7,10**8,10**9,10**10]:
               % timeit f(n)
   ...:     
10 loops, best of 3: 22.8 ms per loop
1 loops, best of 3: 226 ms per loop # roughly ten times previous
1 loops, best of 3: 2.26 s per loop # roughly ten times previous
1 loops, best of 3: 23.3 s per loop # roughly ten times previous
1 loops, best of 3: 4min 18s per loop # roughly ten times previous

使用xrange和python2,我们看到比率大致相同,显然python2总体上要快得多,因为python3 int已被long替换:

In [5]: for n in [10**6,10**7,10**8,10**9,10**10]:
               % timeit f(n)
   ...:     
100 loops, best of 3: 11.3 ms per loop
10 loops, best of 3: 113 ms per loop
1 loops, best of 3: 1.13 s per loop
1 loops, best of 3: 11.4 s per loop
1 loops, best of 3: 1min 56s per loop

运行时间的实际差异似乎与窗口的长度更相关, 而不是与python 3直接相关.当使用unix处理longs与windows有很大不同时,差异很小.所以这是一个特定于平台的问题,如果不是不只是一个蟒蛇.