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

Question

我在对一些 python 代码进行基准测试时发现了一些奇怪的事情。我使用以下函数来测量迭代空 for 循环所花费的速度：

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

f(10**6) 打印关于 0.035，f(10**7) 关于 0.35，f(10**8) 关于 3.5，f(10**9) 关于 35。但是f(10**10)？好了 2000。这当然出乎意料。为什么迭代 10 倍的元素会花费 60 多倍的时间？ python 的 for 循环是怎么回事？这是 python 特有的，还是在很多语言中都存在？

Answer 1

当您超过 10^9 时，您将超出 32 位整数范围。 Python3 然后透明地将您移动到 arbitrary precision integers，分配和使用速度要慢得多。

一般来说，处理如此大的数字是 Python3 比 Python2 慢很多的领域之一（在许多系统上至少有快速的 64 位整数）。从好的方面来说，它使 python 更易于使用，减少了 overflow 类型错误。

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

运行时间的实际差异似乎更多地与 window's long 的大小有关，而不是与 python 直接相关 3. 使用处理 unix 时差异很小longs 与 windows 有很大不同，所以这是一个特定于平台的问题，如果不超过 python 的话。

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

Why are python's for loops so non-linear for large inputs?

benchmarking

for-loop

python-3.x