在python中查找序列长度的开销

Question

我本来打算在python3中找到序列的长度，结果发现range现在是<class type>而不是<type builtin_function_or_method>

因此，range调用似乎在内存中创建了一个生成器，而不需要像python2中那样创建list并填充它的开销（如果我对此有误解或错误，请纠正我）。

我现在的问题是，在计算序列长度时，我调用len(range(start, stop, step))而不是计算int(math.ceil((stop - start) / step))，会有什么显著的改进吗。

这是我将要做的一个粗略的例子：

s = list(range(limit))
s[1] = 0
for i in range(2, sqrtn + 1):
    if s[i]:
        s[i*i: limit: i] = [0] * len(range(i*i, limit, i)) # call to range

上面的计算会比计算长度更有效吗？

from math import ceil
s = list(range(limit))
s[1] = 0
for i in range(2, sqrtn + 1):
if s[i]:
    s[i*i: limit: i] = [0] * int(math.ceil((limit - i*i) / i)) # no range call

Answer 1

在理论上，是的，在实践中，不是。CPython 3.5.0的Windows x64版本上的所有时间（具体时间无关；每种方法的相对时间都很重要）：

>>> from math import ceil
>>> start, stop, step = 100*100, 100000, 100
>>> min(timeit.repeat('(stop - start + (step - 1)) // step', 'from __main__ import start, stop, step', number=100000))
0.016031580173375914
>>> min(timeit.repeat('ceil((stop - start) / step)', 'from __main__ import start, stop, step, ceil', number=100000))
0.024184756985505373
>>> min(timeit.repeat('len(range(start, stop, step))', 'from __main__ import start, stop, step', number=100000))
0.03917228338013956

我已经用几个不同的端点运行了这些测试；如果值变得足够大，以至于无法在Py_ssize_t中进行数学运算，则range和ceil方法会更接近（ceil速度减慢），但纯int数学方法会赢得我运行的每一次测试。并且CCD_ 13和CCD_；对于非常大的数字，range将抛出OverflowError（它的元素不能超过Py_ssize_t所能表示的元素），而ceil（或者更确切地说，ceil之前的浮点除法）将在超过~53位值时出现浮点精度错误。纯int数学既快速又可靠，可能是首选。

也就是说，其他Python解释器（PyPy、IronPython、Jython、Cython）可以是特殊情况下的东西，如range（以及整数数学），并且可以很容易地具有完全不同的性能特征。

这里真正的开销不是len计算。range实际计算长度，并在构建过程中在内部缓存；检索它与任何命名函数调用一样接近免费（所有内置序列也是如此；最坏的情况下，它们必须从C级int构造Python级int，但所有数学运算都做同样的事情）。检索长度的实际成本：

>>> min(timeit.repeat('len(r)', 'from __main__ import start, stop, step; r = range(start, stop, step)', number=100000))
0.0076398965929911355