在Python中高效判断两个列表的交集是否为空

Question

假设我有两个列表，L 和 M。现在我想知道这两个列表是否有共同的元素。用 Python 来问，哪种方法最快呢？

我不在乎它们共享了哪些元素，也不关心有多少个，只想知道它们是否有共同的元素。

比如，在这种情况下：

L = [1,2,3,4,5,6]
M = [8,9,10]

我应该得到 False，也就是没有共同的元素。而在这里：

L = [1,2,3,4,5,6]
M = [5,6,7]

我应该得到 True，也就是有共同的元素。

我希望这个问题很清楚。谢谢！

马努埃尔

Answer 1

首先，如果你不需要这些元素有顺序的话，可以换成 set 类型。

如果你还是需要列表类型的话，可以这样做：0 等于 False。

len(set.intersection(set(L), set(M)))

Answer 2

为了避免构建交集的麻烦，并在我们知道它们相交时尽快给出答案：

m_set = frozenset(M)
return any(x in m_set for x in L)

更新：gnibbler尝试了这个方法，发现用set()代替frozenset()运行得更快。真有意思。

Answer 3

或者更简洁一点

if set(L) & set(M):
    # there is an intersection
else:
    # no intersection

如果你真的需要 True 或 False

bool(set(L) & set(M))

经过一些时间测试，这似乎也是一个不错的选择

m_set=set(M)
any(x in m_set  for x in L)

如果 M 或 L 中的项目不能被哈希，你就得用一种效率较低的方法，比如这样

any(x in M for x in L)

这里是对100个项目列表的时间测试结果。当没有交集时，使用集合的速度明显更快，而当有较大交集时，速度稍慢一些。

M=range(100)
L=range(100,200)

timeit set(L) & set(M)
10000 loops, best of 3: 32.3 µs per loop

timeit any(x in M for x in L)
1000 loops, best of 3: 374 µs per loop

timeit m_set=frozenset(M);any(x in m_set  for x in L)
10000 loops, best of 3: 31 µs per loop

L=range(50,150)

timeit set(L) & set(M)
10000 loops, best of 3: 18 µs per loop

timeit any(x in M for x in L)
100000 loops, best of 3: 4.88 µs per loop

timeit m_set=frozenset(M);any(x in m_set  for x in L)
100000 loops, best of 3: 9.39 µs per loop


# Now for some random lists
import random
L=[random.randrange(200000) for x in xrange(1000)]
M=[random.randrange(200000) for x in xrange(1000)]

timeit set(L) & set(M)
1000 loops, best of 3: 420 µs per loop

timeit any(x in M for x in L)
10 loops, best of 3: 21.2 ms per loop

timeit m_set=set(M);any(x in m_set  for x in L)
1000 loops, best of 3: 168 µs per loop

timeit m_set=frozenset(M);any(x in m_set  for x in L)
1000 loops, best of 3: 371 µs per loop