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。

希望问题清晰明了。 谢谢！

曼努埃尔

- Manuel Araoz

---

请参阅 https://dev59.com/PnA75IYBdhLWcg3wrbC_ 以获得更详尽的解析。not frozenset(L).isdisjoint(M) 似乎是这个问题的最佳解决方案。 - Edward Falk

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

- John La Rooy

---

@gnibbler - 能否证明any()版本不如其他版本高效？它似乎只会在M中查找元素，直到找到L中的一个元素，此时any将返回True并完成。这听起来比事先将L和M都转换为集合更有效。至少在纸面上是这样。 - Chris Lutz

这里，这就是答案。 - jathanism

@Chris，最坏情况是没有交集-O(l*m)。使用集合，我相信它是O(l+m)。 - John La Rooy

@Manuel - 看起来最好的方法是将 一个 列表转换为 set ，以便更快地进行成员测试 (in)，然后基于这种成员测试进行过滤 (x in m_set for x in L)。 @gnibbler，为了完整起见，我们可以使用两个随机构建的列表进行一些测试吗？ （并且对于出色的工作也要加一分） - Chris Lutz

@Darius，看一下最终测试结果。set 比 frozenset 快得多。 - John La Rooy

Answer 2

为了避免构建交点的工作，并在我们得知它们相交时立即给出答案：

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

更新： gnibbler尝试使用set()替换frozenset()后发现运行速度更快。真是意外。

- Darius Bacon

Answer 3

首先，如果您不需要它们有序，则切换到set类型。

如果您仍然需要列表类型，请按照以下方式操作：0 == False

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

- gahooa

---

这似乎不太高效。我的意思是，整个交集都被计算了，对吧？还是它采用惰性求值的方式呢？谢谢！ - Manuel Araoz

@Manuel，当我测试它时，交集计算所需的时间比将列表转换为集合所需的时间少，因此少于总时间的1/3。 - John La Rooy

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.

- tzot