简短的回答:使用not set(a).isdisjoint(b)
,它通常是最快的。
有四种常用方法可以测试两个列表是否a
共享b
任何项目。第一个选项是将两者都转换为集合并检查它们的交集,如下所示:
bool(set(a) & set(b))
因为集合是使用 Python 中的哈希表存储的,所以搜索它们是O(1)
(有关 Python 中运算符复杂性的更多信息,请参见此处)。从理论上讲,这对于列表和中的和对象来说是O(n+m)
平均的。但是 1)它必须首先从列表中创建集合,这可能会花费不可忽略的时间,并且 2)它假设散列冲突在您的数据中是稀疏的。n
m
a
b
第二种方法是使用生成器表达式对列表执行迭代,例如:
any(i in a for i in b)
这允许就地搜索,因此不会为中间变量分配新的内存。它也会在第一次发现时退出。但是in
操作员总是O(n)
在列表中(见这里)。
另一个建议的选项是混合遍历列表中的一个,转换集合中的另一个并测试该集合的成员资格,如下所示:
a = set(a); any(i in a for i in b)
第四种方法是利用isdisjoint()
(frozen)sets 的方法(参见此处),例如:
not set(a).isdisjoint(b)
如果您搜索的元素靠近数组的开头(例如已排序),则首选生成器表达式,因为 sets 交集方法必须为中间变量分配新内存:
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

有趣的是,对于较大的列表大小,生成器表达式要慢得多。这仅适用于 1000 次重复,而不是上图中的 100000 次。当没有共享元素时,此设置也很近似,并且是不相交和集合相交方法的最佳情况。
以下是使用随机数的两个分析(而不是操纵设置以支持一种或另一种技术):

分享机会高:元素随机取自[1, 2*len(a)]
. 分享机会低:元素随机取自[1, 1000*len(a)]
.
到目前为止,该分析假设两个列表的大小相同。如果有两个不同大小的列表,例如a
更小,isdisjoint()
总是更快:

确保a
列表越小,否则性能会下降。在这个实验中,a
列表大小设置为常数5
。
总之:
- 如果列表非常小(< 10 个元素),
not set(a).isdisjoint(b)
总是最快的。
- 如果列表中的元素已排序或具有您可以利用的常规结构,则生成器表达式
any(i in a for i in b)
在大列表大小上是最快的;
- 测试与 的交集
not set(a).isdisjoint(b)
,它总是比 快bool(set(a) & set(b))
。
- 混合“遍历列表,在集合上测试”
a = set(a); any(i in a for i in b)
通常比其他方法慢。
- 当涉及到不共享元素的列表时,生成器表达式和混合器比其他两种方法慢得多。
在大多数情况下,使用该isdisjoint()
方法是最好的方法,因为生成器表达式将花费更长的时间来执行,因为当没有共享元素时它非常低效。