在Python中实现懒加载分区时感到愚蠢

Question

我正在尝试实现一个懒加载的分区功能，这个功能可以在迭代器对象上工作。当迭代器中的某个元素的值发生变化时，它会返回这个迭代器的一部分。这种行为类似于Clojure中的partition-by（虽然输出的语义会有所不同，因为在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

我一直觉得很困惑的是，partition可以是一个普通的列表，而不是一个迭代器，也就是说：

partition = iter([current])
partition = chain(partition,iter([justseen]))
partition = iter([])

可以是：

partition = [current]
partition.append(justseen)
partition = []

Answer 2

为什么不重复使用groupby呢？我觉得它是O(1)的。

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

你实现的groupby和它的不同之处在于，partition是一个专门的迭代器对象，而不是一个由chain组成的链条。