python - 为什么 python itertools "consume"recipe 比调用 next n 次更快？

Question

在 itertools 的 python 文档中，它提供了以下用于推进迭代器 n 步的“配方”:

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)

注意:即使不是从 itertools 导入 islice 我使用上面显示的文档中的 python 等价物定义它，配方仍然更快..

编辑: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 倍

Answer 1

配方之所以更快，是因为它的关键部分(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 通过调用 next on iterator 加上 xrange 上的 for 循环)使成本大约翻倍。