为什么Python的itertools中的“consume”方法比调用next()函数快？

Question

为什么Python的itertools中的“consume”方法比调用next()函数快？

3

在Python的itertools文档中，提供了以下关于迭代器向前推进n步的“recipe”（配方）：

def consume(iterator, n):
    "Advance the iterator n-steps ahead. If n is none, consume entirely."
    # Use functions that consume iterators at C speed.
    if n is None:
        # feed the entire iterator into a zero-length deque
        collections.deque(iterator, maxlen=0)
    else:
        # advance to the empty slice starting at position n
        next(islice(iterator, n, n), None)

我想知道这个配方为什么与这个有根本性的不同（除了处理整个迭代器的方法）：

def other_consume(iterable, n):
    for i in xrange(n):
        next(iterable, None)

我使用timeit确认了，如预期的那样，上述方法要慢得多。是什么让这种优越的性能在这个配方中发挥作用？我知道它使用了islice，但看着islice，它似乎基本上正在做与上面的代码完全相同的事情：

def islice(iterable, *args):
    s = slice(*args)
    it = iter(xrange(s.start or 0, s.stop or sys.maxint, s.step or 1))
    nexti = next(it)
    ### it seems as if this loop yields from the iterable n times via enumerate
    ### how is this different from calling next n times?
    for i, element in enumerate(iterable): 
        if i == nexti:
            yield element
            nexti = next(it)

注意：即使我不使用从上面文档中显示的python等效定义islice，而是从itertools导入它，该配方仍然更快。

编辑：timeit代码在这里：

timeit.timeit('a = iter([random() for i in xrange(1000000)]); consume(a, 1000000)', setup="from __main__ import consume,random", number=10)
timeit.timeit('a = iter([random() for i in xrange(1000000)]); other_consume(a, 1000000)', setup="from __main__ import other_consume,random", number=10)

每次运行时，other_consume 的速度大约慢了2.5倍。

- qwwqwwq

2个回答

0

itertools.islice() 的文档存在缺陷，无法正确处理 start == stop 的边界情况。而正是这种边界情况，consume() 所使用的。

对于 islice(it, n, n)，从 it 中恰好消耗了 n 个元素，但从未产生任何结果。相反，在这些 n 个元素被消耗后，会引发 StopIteration 异常。

然而，你所用来测试的 Python 版本却会立即引发 StopIteration 异常，而根本没有从 it 中消耗任何元素。这使得针对这个纯 Python 版本的计时不正确，速度过快。

这是因为 xrange(n, n, 1) 迭代器会立即引发 StopIteration 异常：

>>> it = iter(xrange(1, 1))
>>> print next(it)
Traceback (most recent call last):
  File "prog.py", line 4, in <module>
    print next(it)
StopIteration

- Martijn Pieters

我认为这只是解释了速度差异的一小部分。使用朴素版本所需的时间大约是itertools.islice配方的10倍。将for i in range(n)替换为枚举循环（当索引等于n时中断）可以将所需时间减少到itertools版本的7倍，但我认为其余部分完全在C语言中实现的逻辑也起到了作用。 - Blckknght

事实上，正是文档中的缺陷使得原始测试存在缺陷。 - Martijn Pieters

实际上，按照我的实现方式，我的消费者从来没有消费过任何东西！ - qwwqwwq

对于回答速度较慢，我深表歉意；在iPhone上进行测试和打字都很慢。 - Martijn Pieters

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Blckknght · Accepted Answer

这个算法更快的原因是它的关键部分（islice，deque）是用C实现的，而不是纯Python。其中一部分原因是C循环比for i in xrange(n)更快。另一部分原因是Python函数调用（例如next()）比它们的C语言等效函数更昂贵。

你从文档中复制的itertools.islice版本是不正确的，它表现出色的原因是使用它的消耗函数没有消耗任何东西。（因此我不显示该版本的测试结果，尽管它非常快！）

这里有几种不同的实现，以便我们可以测试哪种最快：

import collections
from itertools import islice

# this is the official recipe
def consume_itertools(iterator, n):
    "Advance the iterator n-steps ahead. If n is none, consume entirely."
    # Use functions that consume iterators at C speed.
    if n is None:
        # feed the entire iterator into a zero-length deque
        collections.deque(iterator, maxlen=0)
    else:
        # advance to the empty slice starting at position n
        next(islice(iterator, n, n), None)

# your initial version, using a for loop on a range
def consume_qwwqwwq(iterator, n):
    for i in xrange(n):
        next(iterator, None)

# a slightly better version, that only has a single loop:
def consume_blckknght(iterator, n):
    if n <= 0:
        return
    for i, v in enumerate(iterator, start=1):
        if i == n:
            break

我的系统时间（在Windows 7上使用Python 2.7.3 64位）：

>>> test = 'consume(iter(xrange(100000)), 1000)'
>>> timeit.timeit(test, 'from consume import consume_itertools as consume')
7.623556181657534
>>> timeit.timeit(test, 'from consume import consume_qwwqwwq as consume')
106.8907442334584
>>> timeit.timeit(test, 'from consume import consume_blckknght as consume')
56.81081856366518

我的评估是，一个几乎为空的Python循环运行所需的时间，比等价的C语言循环要花费七到八倍的时间。同时在两个序列上进行循环（就像consume_qwwqwwq函数一样，除了对xrange的for循环之外，还调用了iterator的next方法），会使得时间成本大致加倍。