在Python中测试列表是否有相同项目

196 投票

9 回答

157225 浏览

提问于 2025-04-16 00:46

我想检查一个列表中的任意项是否出现在另一个列表中。我可以用下面的代码简单实现这个功能，但我觉得可能有库函数可以做到这一点。如果没有的话，有没有更符合Python风格的方法来实现同样的结果呢？

In [78]: a = [1, 2, 3, 4, 5]

In [79]: b = [8, 7, 6]

In [80]: c = [8, 7, 6, 5]

In [81]: def lists_overlap(a, b):
   ....:     for i in a:
   ....:         if i in b:
   ....:             return True
   ....:     return False
   ....: 

In [82]: lists_overlap(a, b)
Out[82]: False

In [83]: lists_overlap(a, c)
Out[83]: True

In [84]: def lists_overlap2(a, b):
   ....:     return len(set(a).intersection(set(b))) > 0
   ....:

集合操作编程风格列表比较库函数

9 个回答

def lists_overlap(a, b):
  sb = set(b)
  return any(el in sb for el in a)

这个方法在最坏情况下是最优的，复杂度是O(n + m)，而且可能比交集的方法更好，因为any可以提前结束。

举个例子：

lists_overlap([3,4,5], [1,2,3])

当它检查到3 in sb时，就会立刻返回True。

补充说明：还有一种变体（感谢Dave Kirby）：

def lists_overlap(a, b):
  sb = set(b)
  return any(itertools.imap(sb.__contains__, a))

这个方法依赖于imap的迭代器，它是用C语言实现的，而不是用生成器表达式。它还使用sb.__contains__作为映射函数。我不太清楚这会带来多大的性能差异。不过，它仍然会提前结束。

回答于 2025-04-16 由 Python大师

分享举报

def lists_overlap3(a, b):
    return bool(set(a) & set(b))

注意：上面的内容是基于你想要一个布尔值作为答案的前提。如果你只需要一个可以在if语句中使用的表达式，那就直接用if set(a) & set(b):。

回答于 2025-04-16 由 Python大师

分享举报

487

简短回答: 使用 not set(a).isdisjoint(b)，通常是最快的。

有四种常见的方法可以检查两个列表 a 和 b 是否有共同的元素。第一种方法是把两个列表转换成集合，然后检查它们的交集，像这样：

bool(set(a) & set(b))

因为在Python中，集合是用哈希表存储的，所以搜索它们的速度是 O(1)（想了解更多关于Python中操作复杂度的信息，可以查看这里）。理论上，对于列表 a 和 b 中的 n 和 m 个对象，平均复杂度是 O(n+m)。但是

首先必须从列表创建集合，这可能需要不少时间；
假设哈希冲突在你的数据中是稀疏的。

第二种方法是使用生成器表达式对列表进行迭代，比如：

any(i in a for i in b)

这种方法允许就地搜索，因此不会为中间变量分配新的内存。它还会在第一次找到时就停止。但是 in 操作在列表中始终是 O(n)（想了解更多，可以查看这里）。

另一种提议的方法是混合使用，遍历其中一个列表，把另一个列表转换成集合，然后在这个集合中测试成员资格，像这样：

a = set(a); any(i in a for i in b)

第四种方法是利用（冻结）集合的 isdisjoint() 方法（可以查看这里），例如：

not set(a).isdisjoint(b)

如果你要查找的元素在数组的开头附近（例如，它是排序的），那么生成器表达式更有优势，因为集合交集的方法需要为中间变量分配新的内存：

from timeit import timeit
>>> timeit('bool(set(a) & set(b))', setup="a=list(range(1000));b=list(range(1000))", number=100000)
26.077727576019242
>>> timeit('any(i in a for i in b)', setup="a=list(range(1000));b=list(range(1000))", number=100000)
0.16220548999262974

下面是这个例子在不同列表大小下的执行时间图：

注意两个轴都是对数坐标。这代表了生成器表达式的最佳情况。可以看到，isdisjoint() 方法在非常小的列表大小时表现更好，而生成器表达式在较大的列表大小时表现更好。

另一方面，由于混合和生成器表达式的搜索是从开头开始的，如果共享元素系统性地位于数组的末尾（或者两个列表没有共享任何值），那么不相交和集合交集的方法会比生成器表达式和混合方法快得多。

>>> timeit('any(i in a for i in b)', setup="a=list(range(1000));b=[x+998 for x in range(999,0,-1)]", number=1000))
13.739536046981812
>>> timeit('bool(set(a) & set(b))', setup="a=list(range(1000));b=[x+998 for x in range(999,0,-1)]", number=1000))
0.08102107048034668