Python - 在位列表分區

有沒有一種方法來使用標準python 2.7（C++ STL std :: partition style）通過謂詞分區列表？像group_byitertools但不包括額外的數組？我需要遞歸地將數組分爲兩組，基於可變參數條件，並且受RAM的限制。Python - 在位列表分區

我所尋找的是一個函數，如：

partitionCPPStyle(data, startIndex, endIndex, condition)

這將導致具有滿足在開始條件的所有元素，並返回不fullfil第一個元素的索引列表data[startIndex:endIndex]條件。沒有副本，儘可能少使用額外的內存。

我已經結束了寫我自己的實現：

def partitionInPlace(data, startIndex, endIndex, predicate): 
    swapIndex = endIndex 
    index = startIndex 
    while(index < swapIndex): 
     if not predicate(data[index]): 
      temp = data[swapIndex] 
      data[swapIndex] = data[index] 
      data[index] = temp 
      swapIndex = swapIndex-1 
     else: 
      index = index+1 
    return index

有沒有更有效的方式來做到這一點？

來源

2017-04-14 pSoLT

迭代器工具不會複製列表或我完全錯誤？但是，如果你計劃刪除列表中的項目，你將不得不創建一個新的列表，看看列表是不可變的，不能改變。也許看看'dicts'或[ctype.array]（https://docs.python.org/2/library/ctypes.html#arrays）s - 也許你可以用這些做些什麼？ – Torxed

@Toxxed列表是可變的。 – roganjosh

@roganjosh對不起，你說得對。我在頭腦中混合了'tuple'的列表。 – Torxed

這是比較容易實現的 - 但既然你有「條件」（我將使用這裏的術語「斷言」），有併發症：對於沒有複製可言，所形成的結構的唯一途徑可以「知道」一個項目是否在訪問時檢查它 - 這意味着你的索引中會出現「漏洞」。

這很容易理解給出的例子：

a = list(range(20)) 
b = SlicedList(a, slice(10, 20), predicate=lambda x: x%2 
len(b) # will correctly report (5) 
b[0] # will raise ValueError as "10" fails the predicate 
# so, 0-9 are valid indexes for "b", but only the contents 
# that attend the predicate will actually return a value 
# you can safely iterate on b with a "for", though: 
for item in b: 
    print(item) # (11, 13, 15, 17, 19)

迭代，但是，它應該很好地工作。

try: 
    from collections.abc import MutableSequence 
except ImportError: 
    from collections import MutableSequence 


class SlicedList(MutableSequence): 
    def __init__(self, data, slice=None, predicate=None): 
     self.data = data 
     if not slice: 
      slice = __builtins__.slice(0, len(data), 1) 
     self.slice = slice 
     self.predicate = predicate 

    def __getitem__(self, index): 
     if index < 0: 
      raise NotImplementedError("Can't use negative indexes on Sliced lists") 
     real_index = self.slice.start + index * (self.slice.step or 1) 
     item = self.data[real_index] 
     if self.predicate and not self.predicate(item): 
      raise ValueError("Item at position {} does not attend the predicate".format(index)) 
     return item 

    def __setitem__(self, index, value): 
     ... 

    def __delitem__(self, index): 
     ... 

    def __len__(self): 
     if not self.predicate: 
      start, stop, step = self.slice.indices(len(data)) 
      return (stop - start) // (step or 1) 
     count = 0 
     for i in range(self.slice.start, self.slice.stop, self.slice.step or 1): 
      if self.predicate(self.data[i]): 
       count += 1 
     return count 

    def __iter__(self): 
     for i in range(self.slice.start, self.slice.stop, self.slice.step or 1): 
      value =self.data[i] 
      if not self.predicate or self.predicate(value): 
       yield i 

    def insert(self, position, value): 
     ...

另一個提示你是要儘快退出Python 2.7版 - 所有的現代庫和框架運行好的關於Python 3和Python 2是變得非常老化，這些天。下面的代碼可以同時工作，但我必須爲此做出規定。

來源

2017-04-14 13:34:28 jsbueno

它只是一個簡單的快速排序，你可以做你自己的

def partitionCPPStyle(data, a, b, condition): 
    if a>= b:return 
    left = a 
    right = b 
    while left <= right: 
     while left <= right and condition(data[left]): 
      left += 1 
     while left <= right and not condition(data[right]): 
      right -= 1 
     if left <= right: 
      data[left], data[right] = data[right], data[left] 
      left, right = left + 1, right - 1 

def less7(num): 
    return num < 7 
if __name__ == '__main__': 
    data = [2,34,6,1,3232,32] 
    partitionCPPStyle(data, 0, 5, less7) 
    print(data)

它看起來像c.but很容易和好。

來源

2017-04-14 13:47:00 obgnaw

Python - 在位列表分區

回答

相關問題