Python - vor Ort Liste Partition

Question

Gibt es eine Möglichkeit, Liste nach Prädikat an Ort und Stelle mit Standard-Python 2.7 (C++ STL std :: Partitionsstil) zu partitionieren? So etwas wie group_by von itertools, aber ohne zusätzliche Arrays zu killen? Ich muss Array rekursiv in zwei Gruppen basierend auf variadischen Bedingungen partitionieren und ich bin durch die Menge an RAM begrenzt.

Was ich suche, ist eine Funktion wie:

partitionCPPStyle(data, startIndex, endIndex, condition)

, die in data[startIndex:endIndex] Liste führen würde, alle Elemente, die die Bedingung am Anfang genügen, und den Index des ersten Elements zurückkehrt, die nicht fullfil nicht die Bedingung. Keine Kopien, so wenig zusätzlicher Speicher wie möglich.

Ich habe meine eigene Implementierung endete schreiben:

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 

Gibt es eine effizientere Art und Weise, es zu tun?

Answer 1

Dies ist relativ einfach zu implementieren - aber da Sie die "Bedingung" haben (ich werde den Begriff "Prädikat" von hier aus verwenden) gibt es eine Komplikation: für keine Kopie, die einzige Möglichkeit, die resultierende Struktur kann "Wissen", ob ein Element das spezifische Prädikat berücksichtigt, ist es, es zur Zugriffszeit zu überprüfen - das heißt, Sie haben "Löcher" in Ihrer Indizierung.

, die leichter zu verstehen ist ein Beispiel gegeben:

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) 

Für Iteration, aber es sollte gut funktionieren.

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): 
     ... 

Ein weiterer Tipp für Sie ist Python 2.7 so schnell wie möglich zu beenden - alle modernen Bibliotheken und Frameworks laufen Ok auf Python 3 und Python 2 ist wirklich immer in diesen Tagen gealtert. Der Code unten funktioniert an beiden, aber ich musste dafür sorgen.

Answer 2

es ist nur eine einfache QuickSort, Sie können es tun, indem Sie Ihre eigenen

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) 

es aussehen ist c.but es ist einfach und gut.