Чувство глупости при попытке реализовать ленивое разбиение в Python

Question

Я пытаюсь реализовать ленивое разбиение объекта итератора, которое дает срезы итератора, когда функция элемента итератора меняет значения. Это имитирует поведение секционирования Clojure (хотя семантика вывода будет другой, так как Python будет действительно «потреблять» элементы). Моя реализация оптимальна по количеству выполняемых операций, но не по объему памяти. Я не понимаю, почему хорошей реализации понадобится больше, чем O (1) памяти, но моя реализация занимает O (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

Почему бы не повторно использовать groupby? Я думаю, что это O (1).

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

Отличие реализации groupby от вашей заключается в том, что partition является специализированным итератором, а не chain из chain из chain ...

Answer 2

меня беспокоило, что partition может быть обычным списком, а не итератором, т.е.:

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

может быть:

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