python - 尝试在 Python 中实现惰性分区时感觉很愚蠢

Question

我正在尝试实现迭代器对象的惰性分区，当迭代器元素上的函数更改值时，该迭代器对象会生成迭代器的切片。这将模仿 Clojure 的分区行为(尽管输出的语义会有所不同，因为 Python 会真正地“消耗”元素)。我的实现在执行的操作数方面是最佳的，但在所需的内存方面却不是。我不明白为什么一个好的实现需要超过 O(1) 的内存，但我的实现占用了 O(k) 内存，其中 k 是分区的大小。我希望能够处理 k 很大的情况。有谁知道好的实现方案吗？

正确的行为应该是这样的

>>>unagi = [-1, 3, 4, 7, -2, 1, -3, -5]
>>> parts = partitionby(lambda x: x < 0,unagi)
>>> print [[y for y in x] for x in parts]
[[-1], [3, 4, 7], [-2], [1], [-3, -5]]

这是我当前的版本

from itertools import *

def partitionby(f,iterable):
    seq = iter(iterable)
    current = next(seq)
    justseen = next(seq)
    partition = iter([current])
    while True:
        if f(current) == f(justseen): 
            partition = chain(partition,iter([justseen]))
            try:
                justseen = next(seq)
            except StopIteration:
                yield partition
                break
        else:
            yield partition
            current = justseen
            partition = iter([])

Answer 1

为什么不 reuse groupby ？我认为是 O(1)。

def partitionby(f, iterable):
    return (g[1] for g in groupby(iterable, f))

groupby 的实现与您的不同之处在于，partition 是一个专门的迭代器对象，而不是 的 chain chain 的>chain ...