嘗試在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中實現惰性分區時感覺很蠢

回答

相關問題