Python - 就地列表分区

Question

有没有办法使用标准python 2.7(c ++ STL std：:p artition样式(按谓词对列表进行分区？类似于从itertools group_by但没有装箱额外数组的东西？我需要根据可变参数条件递归地将数组分为两组，并且我受到 RAM 数量的限制。

我正在寻找的是这样的功能：

partitionCPPStyle(data, startIndex, endIndex, condition)

这将导致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

有没有更有效的方法？

Answer 1

这相对容易实现 - 但由于你有"条件"(我将从这里开始使用术语"谓词"(，所以有一个复杂的问题：对于根本不复制，结果结构可以"知道"项目是否关注特定谓词的唯一方法是在访问时检查它 - 这意味着您将在索引中存在"漏洞"。

举个例子，这更容易理解：

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现在真的很老。下面的代码可以在两者上工作，但我必须为此做出规定。