python - 在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]

我应该得到真实的。

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

曼努埃尔

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() 代替 freezeset() 运行得更快。什么都知道。

Answer 3

首先，如果您不需要它们订购，那么切换到set类型。

如果你仍然需要列表类型，那么这样做： 0 == False

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

Answer 4

这是我能想到的最通用和最有效的平衡方式（注释应该使代码易于理解）：

import itertools, operator

def _compare_product(list1, list2):
    "Return if any item in list1 equals any item in list2 exhaustively"
    return any(
        itertools.starmap(
            operator.eq,
            itertools.product(list1, list2)))

def do_they_intersect(list1, list2):
    "Return if any item is common between list1 and list2"

    # do not try to optimize for small list sizes
    if len(list1) * len(list2) <= 100: # pick a small number
        return _compare_product(list1, list2)

    # first try to make a set from one of the lists
    try: a_set= set(list1)
    except TypeError:
        try: a_set= set(list2)
        except TypeError:
            a_set= None
        else:
            a_list= list1
    else:
        a_list= list2

    # here either a_set is None, or we have a_set and a_list

    if a_set:
        return any(itertools.imap(a_set.__contains__, a_list))

    # try to sort the lists
    try:
        a_list1= sorted(list1)
        a_list2= sorted(list2)
    except TypeError: # sorry, not sortable
        return _compare_product(list1, list2)

    # they could be sorted, so let's take the N+M road,
    # not the N*M

    iter1= iter(a_list1)
    iter2= iter(a_list2)
    try:
        item1= next(iter1)
        item2= next(iter2)
    except StopIteration: # one of the lists is empty
        return False # ie no common items

    while 1:
        if item1 == item2:
            return True
        while item1 < item2:
            try: item1= next(iter1)
            except StopIteration: return False
        while item2 < item1:
            try: item2= next(iter2)
            except StopIteration: return False

HTH。