Python中将列表在匹配元素处分割的Pythonic和高效方法是什么？

Question

这与Python：如何基于条件拆分列表？以及https://nedbatchelder.com/blog/201306/filter_a_list_into_two_parts.html非常相似，但不同之处在于，我想将列表在第一个未满足谓词的元素处分成两个部分。

>>> divide_list(lambda x: x < 7, list(range(10)))
([0, 1, 2, 3, 4, 5, 6], [7, 8, 9])

>>> divide_list(lambda x: x < 7, [1, 3, 5, 7, 9, 5])
([1, 3, 5], [7, 9, 5])

>>> divide_list(lambda x: x < 7, [7, 9, 5])
([], [7, 9, 5])

>>> divide_list(lambda x: x < 7, [1, 3, 5])
([1, 3, 5], [])

>>> divide_list(lambda x: x['a'], [{'a': True, 'b': 1}, {'a': True}, {'a': False}])
([{'a': True, 'b': 1}, {'a': True}], [{'a': False}])

需要注意的事项：

• 输入列表可能未排序
• 输入列表可能包含重复元素
• 理想情况下，我们不希望多次评估条件（对于每个元素，如果值重复那么没问题）
• 最好接受迭代器作为输入（即只能对输入数据进行一次遍历）
• 返回迭代器是可以接受的

- Tom

---

五年后...那里有另一个答案... - Claudio

Answer 1

我认为除非您确实需要输出迭代器，否则天真的实现可能是最好的选择。如果您的输入流是一个迭代器，并且没有足够的内存一次性将其全部实现等情况时，这可能很有用。

在这种情况下，我认为itertools很棒。我的最初直觉是要做类似于：

# broken  :-(
def divide_iter(pred, lst):
    i = iter(lst)
    yield itertools.takewhile(lst, pred)
    yield i

很不幸，由于多种原因，这并不起作用。 最值得注意的是，它会丢掉一个元素。即使它没有，如果在移动到下一个列表之前没有使用完整个takewhile可迭代对象，可能会遇到问题。 我认为，在处理迭代器时，我们将遇到此第二个问题，所以这有点令人沮丧，但这是我们为逐个元素处理而不是一次性实现整个列表而付出的代价。

相反，让我们考虑根据谓词何时返回true来对项目进行分组。然后groupby变得更加吸引人——唯一的问题是我们需要跟踪谓词是否返回True。 有状态的函数并不好玩，因此我们可以使用一个类，并将绑定方法作为key参数传递给groupby：

import itertools

class _FoundTracker(object):
    def __init__(self, predicate):
        self.predicate = predicate
        self._found = False

    def check_found(self, value):
        if self._found:
            return True
        else:
           self._found = self.predicate(value)
           return self._found

def split_iterable(iterable, predicate):
    tracker = _FoundTracker(predicate)
    for i, (k, group) in enumerate(itertools.groupby(iterable, key=tracker.check_found)):
        yield group
    if i == 0:
        yield iter(())

if __name__ == '__main__':
    for group in split_iterable(xrange(10), lambda x: x < 5):
        print(list(group))

这也可能有一些奇怪的行为... 举个例子，考虑以下内容：

g1, g2 = split_iterable(xrange(10), lambda x: x > 5)
print(list(g1))
print(list(g2))

你会发现你会得到一些非常奇怪的行为 :-). 或者：

g1, g2 = map(list, split_iterable(range(10), lambda x: x > 5))
print(g1)
print(g2)

应该可以正常工作。

- mgilson

---

@downvoter -- 如果您留下评论说明为什么您认为这个答案不有用，或者有什么问题，我很乐意尝试修复任何错误或澄清任何误解。但现在，我不太确定您认为哪里出了问题，所以我也不确定应该把改进的重点放在哪里。 - mgilson

Answer 2

一个启动的天真实现：

def divide_list(pred, lst):
    before, after = [], []
    found = False
    for item in lst:
        if not found:
            if pred(item):
                before.append(item)
            else:
                found = True
        if found:
            after.append(item)
    return before, after

- Tom

Answer 3

为什么要复杂化，如果简单也可以呢？虽然已经提到过，但在我看来，由于不可理解的原因而被放弃考虑：使用itertools takewhile。

以下代码通过了所有断言测试，而且函数本身只需要三行代码：

from itertools import takewhile
def divide_list(pred, lstL):
    header  = list(takewhile(pred, lstL))
    trailer = lstL[len(header):]
    return header, trailer


assert divide_list(lambda x: x < 7, list(range(10))) == ([0, 1, 2, 3, 4, 5, 6], [7, 8, 9])
assert divide_list(lambda x: x < 7, [1, 3, 5, 7, 9, 5]) == ([1, 3, 5], [7, 9, 5])
assert divide_list(lambda x: x < 7, [7, 9, 5]) == ([], [7, 9, 5])
assert divide_list(lambda x: x < 7, [1, 3, 5]) == ([1, 3, 5], [])
assert divide_list(lambda x: x['a'], [{'a': True, 'b': 1}, {'a': True}, {'a': False}]) == ([{'a': True, 'b': 1}, {'a': True}], [{'a': False}])

- Claudio

Answer 4

这是我相对高效的尝试：

from collections import Hashable

def divide_list(pred, list):
    # The predicate may be expensive, so we can
    # store elements that have already been checked
    # in a set for fast verification.
    elements_checked = set()

    # Assuming that every element of the list is of
    # the same type and the list is nonempty, we can
    # store a flag to check if an element is hashable.
    hashable = isinstance(list[0], Hashable)

    for index, element in enumerate(list):
        if hashable and element in elements_checked:
            continue

        if not pred(element):
            return list[:index], list[index:]

        if hashable:
            elements_checked.add(element)

    return list, []

如果你要将这个与其他答案进行基准测试，我认为这将是最快的。

顺便说一句，我喜欢这个问题！

- Jacob G.

---

我认为这过于复杂了，如果一个元素在列表中出现两次，我并不太担心检查pred两次，更多的是我不想像许多filter/filterfalse解决方案那样为每个元素检查两次pred。而且，如果列表元素不可哈希，set()就无法工作，对吗？ - Tom

如果元素不可哈希，则它将检查谓词以查找重复元素，而不是缓存它，这基本上相当于删除集合。理想情况下，您希望保留集合，因为如果存在具有昂贵谓词的许多重复项，则会使其更有效率。 - Jacob G.

如果您愿意，我可以添加一个标志来检查可哈希性，并根据此进行优化，以便使用或不使用集合。 - Jacob G.

我的意思是，divide_list(lambda x: x['a'], [{'a': True, 'b': 1}, {'a': True}, {'a': False}])会引发TypeError: unhashable type: 'dict'错误（将其添加到示例中以澄清其他人的疑惑）。 - Tom

Answer 5

这基本上是您的天真尝试，但它没有使用单独的布尔标志来确定谓词何时失败；它只是使用对第一个列表，然后对另一个列表的引用来进行附加。

def divide_list(pred, lst):
     a, b = [], []
     curr = a
     for x in lst:
         if curr is a and not pred(x):
             curr = b
         curr.append(x)
     return a, b

- chepner