Python：为什么遍历列表比遍历定义其长度的 xrange() 生成器更快？

Question

为什么遍历列表比遍历按列表长度定义的 xrange 生成器更快？

输入：

timeit.timeit('for _ in dummy: continue', setup='dummy=xrange(10000)', number=100000)
timeit.timeit('for _ in dummy: continue', setup='dummy = [0] * 10000', number=100000)

输出：

22.131134033203125
17.916101932525635

我假设这取决于这些操作中有多少是在预编译的 C 代码中本地执行的。

Answer 1

如果我不得不猜测这是因为比较是昂贵的操作。如果 xrange 看起来像这样：

def xrange(limit):
    counter = 0
    while counter < limit:
        counter += 1

那你说的是 10,000 次比较。与遍历列表相反，它只需要在列表末尾引发 StopIteration。

但我不确定内部结构，所以我可能是错的。

Answer 2

我在Python3中做了，结果还是一样。我把range的创作放在了setup里面，为了比较准确

In [1]: timeit.timeit('for _ in a: continue', setup='a=list(range(10000))', number=10000)
Out[1]: 1.195666481000444

In [2]: timeit.timeit('for _ in a: continue', setup='a=range(10000)', number=10000)
Out[2]: 2.4083170039994

我认为主要区别在于 range 在每次迭代时延迟生成 _ 值，而如果您使用列表，它只需要从内存中读取它们。比较

In [3]: timeit.timeit('for _ in range(10000): continue', number=10000)
Out[3]: 4.166428555001403

In [4]: timeit.timeit('for _ in list(range(10000)): continue', number=10000)
Out[4]: 5.800707030000922

我们将创建对象所需的时间考虑在内。这显示了惰性评估的意义。

Answer 3

当我们遍历一个已经创建的列表时，我们实际上是在迭代它的迭代器并每次调用它的 next 方法，它只是根据内部索引从列表中产生下一个项目（it->it_index) maintained by it. i.e No new object is created here. On the other hand range() in Python 3 or xrange() in Python 2 during each iteration Python has to create a new Long object，这可能很贵：

>>> timeit.timeit('for _ in dummy: continue', setup='dummy = xrange(10**4)', number=100000)
8.74455213546753
>>> timeit.timeit('for _ in dummy: continue', setup='dummy = [0] * 10000', number=100000)
7.1642138957977295

如果我们使用 itertools.repeat 和 None 而不是 xrange()，我们会得到一些轻微的改进，因为现在我们不会在每次迭代中创建新对象，只是重复相同的对象。

>>> timeit.timeit('for _ in repeat(None, 10000): continue', setup='from itertools import repeat', number=100000)
6.986715793609619

来自 Raymond Hettinger 的 answer:

It is faster to using itertools.repeat(None, times) to control the number of loops (this avoids creating new, unused integer objects on every iteration).

Answer 4

由于您使用的是 xrange，我假设 Python 2.x。实验的确切设置很重要。

使用虚拟变量（xrange 较慢）

timeit.timeit('for _ in dummy: continue', setup='dummy = range(10000)', number=100000)

13.719306168122216

timeit.timeit('for _ in dummy: continue', setup='dummy = xrange(10000)', number=100000)

15.667266362411738

没有虚拟变量（xrange 更快）

但是，如果我们去掉虚拟变量：

timeit.timeit('for _ in range(10000): continue', number=100000)

20.79111238831547

timeit.timeit('for _ in xrange(10000): continue', number=100000)

15.494247599682467

为什么？

虚拟变量差值

这表明 xrange 变量的设置成本低，但遍历的成本稍高。在第一个实例中，您只设置了一个对象一次，但迭代了 100000 次。在第二个中，你设置了 100000 次，每次迭代一次。有趣 - 因为 xrange 的文档会让您相信相反的情况（我强调）：

Like range(), but instead of returning a list, returns an object that generates the numbers in the range on demand. For looping, this is slightly faster than range() and more memory efficient.

代码差异

查看 the C code where xrange is implemented，我们看到：

...

/*********************** Xrange Iterator **************************/

typedef struct {
    PyObject_HEAD
    long        index;
    long        start;
    long        step;
    long        len;
} rangeiterobject;

static PyObject *
rangeiter_next(rangeiterobject *r)
{
    if (r->index < r->len)
        return PyInt_FromLong(r->start + (r->index++) * r->step);
    return NULL;
}

...

因此，每次从 xrange 获取下一个数字的调用都会导致比较

编辑

注意 - 我使用 range(10000) 与 xrange(10000) 进行对比，但是，使用 OP 的 [0]*10000 和

结果仍然成立

Python：为什么遍历列表比遍历定义其长度的 xrange() 生成器更快？

Python: why is it faster to iterate over a list than iterating over an xrange() generator define on its length?

python

microbenchmark

使用虚拟变量（xrange 较慢）

没有虚拟变量（xrange 更快）

为什么？