itertools.groupby的意外行为

Question

这是观察到的行为:

In [4]: x = itertools.groupby(range(10), lambda x: True)

In [5]: y = next(x)

In [6]: next(x)
---------------------------------------------------------------------------
StopIteration                             Traceback (most recent call last)
<ipython-input-6-5e4e57af3a97> in <module>()
----> 1 next(x)

StopIteration: 

In [7]: y
Out[7]: (True, <itertools._grouper at 0x10a672e80>)

In [8]: list(y[1])
Out[8]: [9]

预期的产出list(y[1])是[0,1,2,3,4,5,6,7,8,9]

这里发生了什么？

我观察到这一点cpython 3.4.2,但其他人已经看到了这个cpython 3.5和IronPython 2.9.9a0 (2.9.0.0) on Mono 4.0.30319.17020 (64-bit).

观察到的行为Jython 2.7.0和pypy:

Python 2.7.10 (5f8302b8bf9f, Nov 18 2015, 10:46:46)
[PyPy 4.0.1 with GCC 4.8.4]

>>>> x = itertools.groupby(range(10), lambda x: True)
>>>> y = next(x)
>>>> next(x)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration
>>>> y
(True, <itertools._groupby object at 0x00007fb1096039a0>)
>>>> list(y[1])
[]

Answer 1

itertools.groupby 文档说明

itertools.groupby(iterable, key=None)

[...]

该操作groupby()类似于Unix中的uniq过滤器.每次键函数的值发生变化时,它都会生成一个中断或新组(这就是为什么通常需要使用相同的键函数对数据进行排序).这种行为不同于SQL的GROUP BY,它聚合了常见元素而不管它们的输入顺序如何.

返回的组本身是一个迭代器,它与底层的iterable共享groupby().因为源是共享的,所以当`groupby()对象被提前时,前一个组不再可见.因此,如果以后需要该数据,则应将其存储为列表 [ - ]

因此,最后一段的假设是生成的列表将是空列表[],因为迭代器已经提前并且已经满足StopIteration; 但在CPython中,结果令人惊讶[9].

这是因为_grouper迭代器滞后于原始迭代器后面的一个项目,这是因为groupby需要提前查看一个项目以查看它是属于当前还是下一个组,但它必须能够稍后将此项目作为第一个项目新组.

然而,currkey和currvalue属性groupby都不能复位时,原来的迭代器被耗尽,所以currvalue仍然指向从迭代器的最后一个项目.

CPython文档实际上包含这个等效代码,它也具有与C版本代码完全相同的行为:

class groupby:
    # [k for k, g in groupby('AAAABBBCCDAABBB')] --> A B C D A B
    # [list(g) for k, g in groupby('AAAABBBCCD')] --> AAAA BBB CC D
    def __init__(self, iterable, key=None):
        if key is None:
            key = lambda x: x
        self.keyfunc = key
        self.it = iter(iterable)
        self.tgtkey = self.currkey = self.currvalue = object()
    def __iter__(self):
        return self
    def __next__(self):
        while self.currkey == self.tgtkey:
            self.currvalue = next(self.it)    # Exit on StopIteration
            self.currkey = self.keyfunc(self.currvalue)
        self.tgtkey = self.currkey
        return (self.currkey, self._grouper(self.tgtkey))
    def _grouper(self, tgtkey):
        while self.currkey == tgtkey:
            yield self.currvalue
            try:
                self.currvalue = next(self.it)
            except StopIteration:
                return
            self.currkey = self.keyfunc(self.currvalue)

值得注意的是,它__next__找到下一组的第一项,并将其键存储到其中,self.currkey并将其值存储到其中self.currvalue.但关键是这条线

self.currvalue = next(self.it)    # Exit on StopIteration

当next抛出时StopItertion,self.currvalue仍然包含前一组的最后一个键.现在,当y[1]进入a时list,它首先产生值self.currvalue,然后才next()在底层迭代器上运行(并StopIteration再次遇到).

尽管文档中有Python等价物,但其行为与CPython中的权威C代码实现完全相同,IronPython,Jython和PyPy给出了不同的结果.