从另一个列表中删除出现在一个列表中的所有元素

假设我有两个列表，l1和l2。我想执行l1 - l2，它将返回l1中不在l2中的所有元素。

我可以想出一个简单的循环方法来做这个，但那真的很低效。python式的高效方法是什么?

例如，如果我有l1 = [1,2,6,8] and l2 = [2,3,5,8]， l1 - l2应该返回[1,6]

474097 次浏览
小开

Python有一个名为列表理解的语言特性，它非常适合使这类事情变得非常简单。下面的语句完全是你想要的，并将结果存储在l3中:

l3 = [x for x in l1 if x not in l2]

l3将包含[1, 6]。

小开

一种方法是使用集合:

>>> set([1,2,6,8]) - set([2,3,5,8])
set([1, 6])

但是请注意，集合不会保留元素的顺序，并且会删除任何重复的元素。元素也需要是可哈希的。如果这些限制是可以容忍的，那么这通常是最简单和性能最高的选项。

小开

使用Python set类型。这是最Pythonic的。：）

此外，由于它是原生的，它也应该是最优化的方法。

看到的:

http://docs.python.org/library/stdtypes.html#set

http://docs.python.org/library/sets.htm(适用于较旧的python)

# Using Python 2.7 set literal format.
# Otherwise, use: l1 = set([1,2,6,8])
#
l1 = {1,2,6,8}
l2 = {2,3,5,8}
l3 = l1 - l2
小开

扩展Donut的答案和这里的其他答案，通过使用生成器推导式而不是列表推导式，以及使用set数据结构(因为in操作符在列表上是O(n)，但在集合上是O(1))，您可以得到更好的结果。

这里有一个函数适合你:

def filter_list(full_list, excludes):
s = set(excludes)
return (x for x in full_list if x not in s)

结果将是一个可迭代对象，它将惰性地获取过滤后的列表。如果你需要一个真正的列表对象(例如，如果你需要在结果上执行len())，那么你可以很容易地像这样构建一个列表:

filtered_list = list(filter_list(full_list, excludes))
小开

备选方案:

reduce(lambda x,y : filter(lambda z: z!=y,x) ,[2,3,5,8],[1,2,6,8])
小开

性能比较

比较这里提到的所有答案在Python 3.9.1和Python 2.7.16上的性能。

Python 3.9.1

答案按表现顺序列出:

  1. < p > # EYZ1

    mquadri$ python3 -m timeit -s "l1 = set([1,2,6,8]); l2 = set([2,3,5,8]);" "l1 - l2"
5000000 loops, best of 5: 91.3 nsec per loop
  2. < p > # EYZ1

    mquadri$ python3 -m timeit -s "l1 = set([1,2,6,8]); l2 = set([2,3,5,8]);" "l1.difference(l2)"
2000000 loops, best of 5: 133 nsec per loop
  3. < p > # EYZ1

     mquadri$ python3 -m timeit -s "l1 = [1,2,6,8]; l2 = set([2,3,5,8]);" "[x for x in l1 if x not in l2]"
1000000 loops, best of 5: 366 nsec per loop
  4. < p > # EYZ0

     mquadri$ python3 -m timeit -s "l1 = [1,2,6,8]; l2 = [2,3,5,8];" "[x for x in l1 if x not in l2]"
500000 loops, best of 5: 489 nsec per loop

  5. Daniel Pryden's <强>生成器表达式与set为基础的查找和类型转换到list - (每循环583 nsec):显式类型转换到list以获得最终对象为list，根据op的要求。如果生成器表达式被列表理解取代，它将与Moinuddin Quadri's列表理解与set基于查找。相同

     mquadri$ mquadri$ python3 -m timeit -s "l1 = [1,2,6,8]; l2 = set([2,3,5,8]);" "list(x for x in l1 if x not in l2)"
500000 loops, best of 5: 583 nsec per loop

  6. Moinuddin Quadri's using filter()和显式类型转换到list(需要在Python 3中显式类型转换。x，它返回迭代器)- (每循环681 nsec)

     mquadri$ python3 -m timeit -s "l1 = [1,2,6,8]; l2 = set([2,3,5,8]);" "list(filter(lambda x: x not in l2, l1))"
500000 loops, best of 5: 681 nsec per loop

  7. Akshay Hazari's 使用组合#EYZ0 + filter -(3.36 usec每个循环):从Python 3显式类型转换到list。X开始返回返回迭代器。我们还需要导入functools，以便在Python 3.x中使用reduce

     mquadri$ python3 -m timeit "from functools import reduce; l1 = [1,2,6,8]; l2 = [2,3,5,8];" "list(reduce(lambda x,y : filter(lambda z: z!=y,x) ,l1,l2))"
100000 loops, best of 5: 3.36 usec per loop

Python 2.7.16

答案按表现顺序列出:

  1. < p > # EYZ1

    mquadri$ python -m timeit -s "l1 = set([1,2,6,8]); l2 = set([2,3,5,8]);" "l1 - l2"
10000000 loops, best of 3: 0.0783 usec per loop
  2. < p > # EYZ1

    mquadri$ mquadri$ python -m timeit -s "l1 = set([1,2,6,8]); l2 = set([2,3,5,8]);" "l1.difference(l2)"
10000000 loops, best of 3: 0.117 usec per loop
  3. < p > # EYZ1

     mquadri$ python -m timeit -s "l1 = [1,2,6,8]; l2 = set([2,3,5,8]);" "[x for x in l1 if x not in l2]"
1000000 loops, best of 3: 0.246 usec per loop
  4. < p > # EYZ0

     mquadri$ python -m timeit -s "l1 = [1,2,6,8]; l2 = [2,3,5,8];" "[x for x in l1 if x not in l2]"
1000000 loops, best of 3: 0.372 usec per loop
  5. < p > # EYZ1

     mquadri$ python -m timeit -s "l1 = [1,2,6,8]; l2 = set([2,3,5,8]);" "filter(lambda x: x not in l2, l1)"
1000000 loops, best of 3: 0.593 usec per loop

  6. Daniel Pryden's <强>生成器表达式与set为基础的查找和类型转换到list - (每循环0.964):显式类型转换到list以获得最终对象为list，根据op的要求。如果生成器表达式被列表理解取代，它将与Moinuddin Quadri's列表理解与set基于查找。相同

     mquadri$ python -m timeit -s "l1 = [1,2,6,8]; l2 = set([2,3,5,8]);" "list(x for x in l1 if x not in l2)"
1000000 loops, best of 3: 0.964 usec per loop
  7. < p > # EYZ2

     mquadri$ python -m timeit "l1 = [1,2,6,8]; l2 = [2,3,5,8];" "reduce(lambda x,y : filter(lambda z: z!=y,x) ,l1,l2)"
100000 loops, best of 3: 2.78 usec per loop
小开

使用集理解 {x for x in l2}或set(l2)获取set，然后使用列表理解获取list

l2set = set(l2)
l3 = [x for x in l1 if x not in l2set]

基准测试代码:

import time


l1 = list(range(1000*10 * 3))
l2 = list(range(1000*10 * 2))


l2set = {x for x in l2}


tic = time.time()
l3 = [x for x in l1 if x not in l2set]
toc = time.time()
diffset = toc-tic
print(diffset)


tic = time.time()
l3 = [x for x in l1 if x not in l2]
toc = time.time()
difflist = toc-tic
print(difflist)


print("speedup %fx"%(difflist/diffset))

基准测试结果:

0.0015058517456054688
3.968189239501953
speedup 2635.179227x
小开

Python 3.8上的集合和列表理解基准

(加起来就是Moinuddin Quadri的基准)

tldr:使用Arkku集合解，相比之下，它甚至比承诺的还要快!

根据列表检查现有文件

在我的例子中，我发现对于一个根据列表检查现有文件名的实际应用程序，使用Arkku集合解要比使用python式列表理解快。

列表理解:

%%time
import glob
existing = [int(os.path.basename(x).split(".")[0]) for x in glob.glob("*.txt")]
wanted = list(range(1, 100000))
[i for i in wanted if i not in existing]

墙壁时间:28.2秒

集

%%time
import glob
existing = [int(os.path.basename(x).split(".")[0]) for x in glob.glob("*.txt")]
wanted = list(range(1, 100000))
set(wanted) - set(existing)

壁时间:689毫秒

小开

使用# EYZ0:

您可以使用set.difference()来获取新的集合，其中包含集合中其他集合中不存在的元素。例如，set(A).difference(B)将返回包含在A中出现的项目的集合，而不是在B中。例如:

>>> set([1,2,6,8]).difference([2,3,5,8])
{1, 6}

它是< em > Arkku的回答< / em > (对集差使用算术减法-运算符)中提到的函数方法得到set的差值。

由于集是无序的，您将失去初始列表中元素的顺序。# EYZ1

使用列表理解和基于set的查找

如果你想要维护从初始列表开始的排序，那么基于甜甜圈的列表理解的答案就可以了。但是，您可以从已接受的答案在内部使用set中选择获得更好的性能来检查元素是否存在于其他列表中。例如:

l1, l2 = [1,2,6,8], [2,3,5,8]
s2 = set(l2)  # Type-cast `l2` to `set`


l3 = [x for x in l1 if x not in s2]
#   ^ Doing membership checking on `set` s2

如果你想知道为什么set的会员资格检查比list更快，请阅读什么使得集合比列表快?< / em >

使用filter()和lambda表达式

这是另一个替代使用filter()与lambda表达式。在这里添加它只是为了参考，但它不是有效的性能:

>>> l1 = [1,2,6,8]
>>> l2 = set([2,3,5,8])


#     v  `filter` returns the a iterator object. Here I'm type-casting
#     v  it to `list` in order to display the resultant value
>>> list(filter(lambda x: x not in l2, l1))
[1, 6]
小开

试试这个:

l1=[1,2,6,8]
l2=[2,3,5,8]
r=[]
for x in l1:
if x in l2:
continue
r=r+[x]
print(r)
小开

使用filterfalse 没有 lambda表达式

当使用像filterfalse2或filterfalse3这样的函数和类似的filterfalse4函数时，你通常可以通过避免使用# eyz3 -表达式和使用已经存在的函数来节省性能。list和set的实例定义了一个用于容器检查的# eyz15方法。# eyz7 -操作符在底层调用这个方法，因此使用x in l2可以用l2.__contains__(x)代替。通常这种替换并不是真的更漂亮，但在这个特定的情况下，当与filterfalse结合使用时，它可以让我们获得比使用# eyz3 -表达式更好的性能:

>>> from itertools import filterfalse
>>> l1 = [1, 2, 6, 8]
>>> l2 = [2, 3, 5, 8]
>>> list(filterfalse(l2.__contains__, l1))
[1, 6]

filterfalse创建一个迭代器，当用作l2.__contains__的参数时，该迭代器将产生返回false的所有元素。

Sets有一个更快的__contains__实现，所以更好的是:

>>> from itertools import filterfalse
>>> l1 = [1, 2, 6, 8]
>>> l2 = set([2, 3, 5, 8])
>>> list(filterfalse(l2.__contains__, l1))
[1, 6]

性能

使用列表:

$  python3 -m timeit -s "from itertools import filterfalse; l1 = [1,2,6,8]; l2 = set([2,3,5,8]);" "list(filterfalse(l2.__contains__, l1))"
500000 loops, best of 5: 522 nsec per loop

使用设置:

$ python3 -m timeit -s "from itertools import filterfalse; l1 = [1,2,6,8]; l2 = set([2,3,5,8]);" "list(filterfalse(l2.__contains__, l1))"
1000000 loops, best of 5: 359 nsec per loop
小开

通过利用字典的有序属性来维持顺序(Python 3.7+)

注意:Python 3.6中dicts的参考实现按照插入顺序维护键，但规范不保证这一点。对于3.7及更高版本，添加了这个保证。

dict函数的键类似于set;重复项被隐式过滤掉，由于散列，查找是高效的。因此，我们可以实现一个“设置差异”;通过使用l1作为键来构建字典，然后删除出现在l2中的任何键。这维持了秩序并使用了一种快速的算法，但会产生相当数量的常量开销。

d = dict.fromkeys(l1)
for i in l2:
try:
del d[i]
except KeyError:
pass
l3 = list(d.keys())
小开

如果你想要那种行为，集合方法是最好的。如果您不想删除列表l1中仅在l2中存在过一次的元素的所有实例，那么这些set操作将导致错误的结果。假设你在l1中有重复的元素，甚至在l2中也有重复的元素，并且想要两个列表l1 - l2的实际差值，同时保持其余元素的顺序:

l1 = [1, 2, 3, 4, 5, 5, 6, 5, 5, 2]
l2 = [1, 2, 2, 5]
_ = [l1.remove(item) for item in l2 if item in l1] # discard return value
print(l1) # [3, 4, 5, 6, 5, 5]
  1. 注意，这将明显比设置操作慢，只在用例需要时使用它
  2. 如果你不想修改原来的列表-先创建一个列表的副本

提交答案