在python中有效地知道两个列表的交集是否为空

Question

假设我有两个列表,L和M.现在我想知道它们是否共享一个元素.如果他们共享一个元素,这将是最快的询问方式(在python中)？我不关心他们分享哪些元素,或者多少,只要他们分享或不分享.

例如,在这种情况下

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

我应该得到假,在这里:

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

我应该成真.

我希望问题清楚.谢谢!

曼努埃尔

Answer 1

或者更简洁

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

Answer 2

为了避免构建交集的工作,并在我们知道它们相交时立即产生答案:

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

更新: gnibbler尝试了这一点,发现用set()代替frozenset()运行得更快.Whaddayaknow.