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

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

正确的行为应该是这样的

>>>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([])

来源

2011-04-29 Gabriel Mitchell

请注意，“分区”通常是指在给定函数的情况下将可迭代项分成两部分的功能操作，因此您的名字可能会令人困惑。 http://zvon.org/other/haskell/Outputlist/partition_f.html – tokland 2011-04-29 19:59:09

为什么不reuse groupby？我认为这是O（1）。

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

groupby的执行与你的不同之处在于partition是一种专门的迭代器对象，而不是的chainchain一个chain ...

来源

2011-04-29 18:35:34 kennytm

感谢KennyTM！我想我需要花一些时间来了解itertools。在太空中是O（1）。 – 2011-04-29 18:50:48

好吧，它通常看起来像（g为（k，g）在groupby（iterable，f）中） – tokland 2011-04-29 19:56:38

它是窃听我，partition可能是一般的列表，而不是一个迭代器即：

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

可能是：

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

来源

2011-04-29 18:42:35

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

回答

相关问题