假设我有一个列表,还有一个筛选函数。使用类似以下的方法:
>>> filter(lambda x: x > 10, [1,4,12,7,42])
[12, 42]
我可以获取符合条件的元素。有没有一种函数能够输出两个列表,一个包含匹配的元素,另一个包含剩余的元素?我可以调用 filter()
函数两次,但那样有点丑 :)编辑: 元素的顺序应该保持不变,并且可能会多次具有相同的元素。
假设我有一个列表,还有一个筛选函数。使用类似以下的方法:
>>> filter(lambda x: x > 10, [1,4,12,7,42])
[12, 42]
我可以获取符合条件的元素。有没有一种函数能够输出两个列表,一个包含匹配的元素,另一个包含剩余的元素?我可以调用 filter()
函数两次,但那样有点丑 :)编辑: 元素的顺序应该保持不变,并且可能会多次具有相同的元素。
试试这个:
def partition(pred, iterable):
trues = []
falses = []
for item in iterable:
if pred(item):
trues.append(item)
else:
falses.append(item)
return trues, falses
使用方法:
>>> trues, falses = partition(lambda x: x > 10, [1,4,12,7,42])
>>> trues
[12, 42]
>>> falses
[1, 4, 7]
在itertools的示例中也提供了一种实现建议:
from itertools import filterfalse, tee
def partition(pred, iterable):
'Use a predicate to partition entries into false entries and true entries'
# partition(is_odd, range(10)) --> 0 2 4 6 8 and 1 3 5 7 9
t1, t2 = tee(iterable)
return filterfalse(pred, t1), filter(pred, t2)
这个方案来自于Python 3.x的文档。在Python 2.x中,filterfalse
被称为ifilterfalse
。
partition
在itertools的配方中实际上有一个实现:http://docs.python.org/dev/library/itertools.html#itertools-recipes - Mark Byersitertools
可能不值得:它会对谓词进行两倍的调用,因此需要几乎两倍的时间;而且代码也不够清晰。 - joeln>>> def partition(l, p):
... return reduce(lambda x, y: (x[0]+[y], x[1]) if p(y) else (x[0], x[1]+[y]), l, ([], []))
...
>>> partition([1, 2, 3, 4, 5], lambda x: x < 3)
([1, 2], [3, 4, 5])
以下是一个稍微丑陋一些但更快的版本:
def partition(l, p):
return reduce(lambda x, y: x[0].append(y) or x if p(y) else x[1].append(y) or x, l, ([], []))
这是第二次编辑,但我认为它很重要:
def partition(l, p):
return reduce(lambda x, y: x[not p(y)].append(y) or x, l, ([], []))
第二种和第三种方法与迭代法相比速度一样快,但代码更少。p(y)
检查条件,然后将当前元素附加到第一个或第二个列表中。如果您不喜欢x [0] + [y]
语法,则可以像第二个解决方案中那样使用x [0] .append(y)
。我认为最后一个解决方案最不理想,因为它依赖于将布尔值(not p(y)
)解释为整数索引。 - joschobject.mutate()或object
- 我有滥用它的最伟大计划!非常感谢! - gboffi这是最简单和最快的方法。
def partition(pred, iterable): trues = [] falses = [] for item in iterable: if pred(item): trues.append(item) else: falses.append(item) return trues, falses
基准测试不同的方法
已经提出的不同方法可大致分为三类:
1. 通过 `lis.append` 进行简单列表操作,返回包含两个列表的二元组。 2. 通过函数式方法中介使用 `lis.append` ,返回包含两个列表的二元组。 3. 使用 `itertools` 精细文档中给出的规范配方,返回包含两个生成器的二元组(泛指)。
以下是三种技术的普通实现,首先是函数式方法,然后是 itertools,最后是直接列表操作的两种不同实现,其中一个选择使用“False为零,True为一”的技巧。
请注意这是Python3 - 因此,`reduce` 来自`functools` - 并且OP请求一个像`(positives, negatives)`这样的元组,但我所有的实现都返回`(negatives, positives)`...我们需要一个谓词来应用于我们的列表和列表(再次,口语化表述),以便进行操作。
$ ipython Python 3.6.2 |Continuum Analytics, Inc.| (default, Jul 20 2017, 13:51:32) Type 'copyright', 'credits' or 'license' for more information IPython 6.1.0 -- An enhanced Interactive Python. Type '?' for help. In [1]: import functools ...: ...: def partition_fu(p, l, r=functools.reduce): ...: return r(lambda x, y: x[p(y)].append(y) or x, l, ([], [])) ...: In [2]: import itertools ...: ...: def partition_it(pred, iterable, ...: filterfalse=itertools.filterfalse, ...: tee=itertools.tee): ...: t1, t2 = tee(iterable) ...: return filterfalse(pred, t1), filter(pred, t2) ...: In [3]: def partition_li(p, l): ...: a, b = [], [] ...: for n in l: ...: if p(n): ...: b.append(n) ...: else: ...: a.append(n) ...: return a, b ...: In [4]: def partition_li_alt(p, l): ...: x = [], [] ...: for n in l: x[p(n)].append(n) ...: return x ...:
我们需要一个谓词来应用于我们的列表和列表(再次,口语化表述),以便进行操作。
为了解决由于测试In [5]: p = lambda n:n%2 In [6]: five, ten = range(50000), range(100000)
itertools
方法而引发的问题,这个问题是由joeln在2013年10月31日6:17报告的。
“胡说八道。你计算了在filterfalse
和filter
中构造生成器所需的时间,但你并没有迭代输入,也没有调用pred
!itertools
配方的优点在于它不会让任何列表具体化,也不会超前查看比必要更多的输入。它将两次调用pred
,并且需要的时间几乎是Byers等人的两倍。”
“我考虑过一个空循环,只是实例化由不同分区函数返回的两个可迭代元素中的所有对。”
“首先,我们使用两个固定列表来了解所涉及的负载量(使用非常方便的IPython魔术命令%timeit
)。”In [7]: %timeit for e, o in zip(five, five): pass 4.21 ms ± 39.4 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
接下来我们会依次使用不同的实现方式。
In [8]: %timeit for e, o in zip(*partition_fu(p, ten)): pass 53.9 ms ± 112 µs per loop (mean ± std. dev. of 7 runs, 10 loops each) In [9]: %timeit for e, o in zip(*partition_it(p, ten)): pass 44.5 ms ± 3.84 ms per loop (mean ± std. dev. of 7 runs, 10 loops each) In [10]: %timeit for e, o in zip(*partition_li(p, ten)): pass 36.3 ms ± 101 µs per loop (mean ± std. dev. of 7 runs, 10 loops each) In [11]: %timeit for e, o in zip(*partition_li_alt(p, ten)): pass 37.3 ms ± 109 µs per loop (mean ± std. dev. of 7 runs, 10 loops each) In [12]:
评论
最简单的方法也是最快的方法。
使用
x[p(n)]
技巧是没有用的,因为每一步都要对数据结构进行索引,导致你有一个轻微的惩罚——但如果你想说服一个正在pythonizing过程中的文化衰落的幸存者,这个技巧还是很好知道的。函数式方法,即操作上等同于另一种
append
实现方式,比较慢,慢了约50%,可能是因为我们对每个列表元素都需要进行额外的函数调用,相对于谓词评估而言。
itertools
方法具有(通常的)优点: ❶不会实例化可能很大的列表,❷如果你退出了消费者循环,输入列表就不会被完全处理,但当我们使用它时,由于需要在tee
的两端应用谓词,所以会更慢。旁白
我爱上了
object.mutate() or object
这个习语,这是由Marii在他们的答案中展示了一种函数式方法来解决问题——我担心,早晚会滥用它。脚注
[1]截至今天(2017年9月14日)被接受并得到最高票数——但当然我对我的这个答案寄予厚望!
django.utils.functional.partition
的解决方案:def partition(predicate, values):
"""
Splits the values into two sets, based on the return value of the function
(True/False). e.g.:
>>> partition(lambda x: x > 3, range(5))
[0, 1, 2, 3], [4]
"""
results = ([], [])
for item in values:
results[predicate(item)].append(item)
return results
>>> l=range(6)
>>> key=lambda x: x % 2 == 0
>>> from itertools import groupby
>>> {k:list(g) for k,g in groupby(sorted(l,key=key),key=key)}
{False: [1, 3, 5], True: [0, 2, 4]}
如果你的列表中没有重复元素,你可以使用集合(set):
>>> a = [1,4,12,7,42]
>>> b = filter(lambda x: x > 10, [1,4,12,7,42])
>>> no_b = set(a) - set(b)
set([1, 4, 7])
>>> no_b = [i for i in a if i not in b]
O(n*m)
,若元素数量超过几十个,则速度会很慢。将 b
转换成集合 b_set = set(b)
并在列表推导式中加入条件 if i not in b
将会改善这种情况。 - user395760我刚有了这个需求。我不太喜欢itertools方案,因为它需要两次经过数据处理。以下是我的实现:
def filter_twoway(test, data):
"Like filter(), but returns the passes AND the fails as two separate lists"
collected = {True: [], False: []}
for datum in data:
collected[test(datum)].append(datum)
return (collected[True], collected[False])
from itertools import ifilterfalse
def filter2(predicate, iterable):
return filter(predicate, iterable), list(ifilterfalse(predicate, iterable))
iterable
是单次可迭代的话,这个方法就不起作用。 - Giuseppe Ottavianotee()
,它会复制可迭代对象,以便它也可以与单次遍历的可迭代对象一起使用。 - Giuseppe Ottavianopartition()
函数(我不知道),所以我将保持原样并点赞其他解决方案。 - Tamás现有的答案要么将可迭代对象分成两个列表,要么将其分成两个效率低下的生成器。这里提供了一种高效地将可迭代对象分成两个生成器的实现方法,即谓词函数对可迭代对象中的每个元素最多只调用一次。您可能希望使用此版本的一个例子是,如果您需要使用昂贵的谓词来分割非常大(甚至是无限)的可迭代对象。
from collections import deque
def partition(pred, iterable):
seq = iter(iterable)
true_buffer = deque()
false_buffer = deque()
def true_iter():
while True:
while true_buffer:
yield true_buffer.popleft()
item = next(seq)
if pred(item):
yield item
else:
false_buffer.append(item)
def false_iter():
while True:
while false_buffer:
yield false_buffer.popleft()
item = next(seq)
if not pred(item):
yield item
else:
true_buffer.append(item)
return true_iter(), false_iter()
from itertools import count
from random import random
odds, evens = partition(lambda n: n % 2, count())
for _ in range(500):
if random() < 0.5:
print(next(odds))
else:
print(next(evens))
每个人都认为自己的解决方案是最好的,所以我决定使用timeit来测试所有的解决方案。我使用"def is_odd(x): return x & 1"作为我的谓词函数,"xrange(1000)"作为可迭代对象。这是我使用的Python版本:
Python 2.7.3 (v2.7.3:70274d53c1dd, Apr 9 2012, 20:52:43)
[GCC 4.2.1 (Apple Inc. build 5666) (dot 3)] on darwin
这里是我的测试结果:
Mark Byers
1000 loops, best of 3: 325 usec per loop
cldy
1000 loops, best of 3: 1.96 msec per loop
Dan S
1000 loops, best of 3: 412 usec per loop
TTimo
1000 loops, best of 3: 503 usec per loop
import itertools
def partition(pred, iterable,
# Optimized by replacing global lookups with local variables
# defined as default values.
filter=itertools.ifilter,
filterfalse=itertools.ifilterfalse,
tee=itertools.tee):
'Use a predicate to partition entries into false entries and true entries'
# partition(is_odd, range(10)) --> 0 2 4 6 8 and 1 3 5 7 9
t1, t2 = tee(iterable)
return filterfalse(pred, t1), filter(pred, t2)
100000 loops, best of 3: 2.58 usec per loop
itertools的示例代码至少比其他代码快100倍!教训是,不要重复造轮子。
filterfalse
和 filter
中构建生成器所需的时间,但是你没有迭代输入或调用pred
!使用itertools
配方的优点在于它不会实现任何列表,也不会比必要时查看输入更多。 它两次调用pred
并且比Byers等人的方法慢近两倍。 - joeln
[(pred(x), x) for x in seq]
。 - Jochen Ritzel[(pred(x), x) for x in seq]
会给我一个类似于[(True, elem1), (False, elem2), ...]
的列表,但这不是我想要的。 - F'x