python - 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 上观察到这个，但其他人在 Mono 4.0 上用 cpython 3.5 和 IronPython 2.9.9a0 (2.9.0.0) 看到了这个.30319.17020(64 位)。

在 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)

[...]

The operation of groupby() is similar to the uniq filter in Unix. It generates a break or new group every time the value of the key function changes (which is why it is usually necessary to have sorted the data using the same key function). That behavior differs from SQL’s GROUP BY which aggregates common elements regardless of their input order.

The returned group is itself an iterator that shares the underlying iterable with groupby(). Because the source is shared, when the `groupby() object is advanced, the previous group is no longer visible. So, if that data is needed later, it should be stored as a list [--]

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

---

这是因为 _grouper iterator一个项目滞后于原始迭代器，这是因为 groupby 需要提前查看一个项目以查看它是属于当前组还是下一个组，但它必须能够稍后产生该项目作为新组的第一项。

然而，当 original iterator is exhausted 时，groupby 的 currkey 和 currvalue 属性不会重置, 所以 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] 被制成一个 list 时，它首先 产生 self.currvalue 的值，然后才在底层迭代器上运行 next()(并再次遇到 StopIteration)。

---

即使文档中有 Python 等效项，其行为与 CPython、IronPython、Jython 和 PyPy 中的权威 C 代码实现完全一样，但会给出不同的结果。