164

我想检查一个列表中的任何项目是否存在于另一个列表中。我可以用下面的代码简单地做到这一点,但我怀疑可能有一个库函数可以做到这一点。如果没有,是否有更 Pythonic 的方法来实现相同的结果。

In [78]: a = [1, 2, 3, 4, 5]

In [79]: b = [8, 7, 6]

In [80]: c = [8, 7, 6, 5]

In [81]: def lists_overlap(a, b):
   ....:     for i in a:
   ....:         if i in b:
   ....:             return True
   ....:     return False
   ....: 

In [82]: lists_overlap(a, b)
Out[82]: False

In [83]: lists_overlap(a, c)
Out[83]: True

In [84]: def lists_overlap2(a, b):
   ....:     return len(set(a).intersection(set(b))) > 0
   ....: 
4

9 回答 9

405

简短的回答:使用not set(a).isdisjoint(b),它通常是最快的。

有四种常用方法可以测试两个列表是否a共享b任何项目。第一个选项是将两者都转换为集合并检查它们的交集,如下所示:

bool(set(a) & set(b))

因为集合是使用 Python 中的哈希表存储的,所以搜索它们是O(1)(有关 Python 中运算符复杂性的更多信息,请参见此处)。从理论上讲,这对于列表和中的和对象来说是O(n+m)平均的。但是 1)它必须首先从列表中创建集合,这可能会花费不可忽略的时间,并且 2)它假设散列冲突在您的数据中是稀疏的。nmab

第二种方法是使用生成器表达式对列表执行迭代,例如:

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()方法是最好的方法,因为生成器表达式将花费更长的时间来执行,因为当没有共享元素时它非常低效。

于 2013-07-18T23:06:05.867 回答
27
def lists_overlap3(a, b):
    return bool(set(a) & set(b))

注意:以上假设您想要一个布尔值作为答案。如果您只需要在语句中使用的if表达式,只需使用if set(a) & set(b):

于 2010-07-03T02:21:39.280 回答
11
def lists_overlap(a, b):
  sb = set(b)
  return any(el in sb for el in a)

any这是渐近最优的(最坏情况 O(n + m)),并且由于的​​短路,可能比交集方法更好。

例如:

lists_overlap([3,4,5], [1,2,3])

一旦到达就会返回 True3 in sb

编辑:另一种变化(感谢戴夫柯比):

def lists_overlap(a, b):
  sb = set(b)
  return any(itertools.imap(sb.__contains__, a))

这依赖于imap用 C 实现的迭代器,而不是生成器理解。它也sb.__contains__用作映射函数。我不知道这会带来多大的性能差异。它仍然会短路。

于 2010-07-03T02:40:59.747 回答
5

您还可以使用any列表推导:

any([item in a for item in b])
于 2010-07-03T02:23:42.367 回答
3

在 python 2.6 或更高版本中,您可以执行以下操作:

return not frozenset(a).isdisjoint(frozenset(b))
于 2012-11-13T10:49:47.933 回答
2

您可以使用任何内置函数 /wa 生成器表达式:

def list_overlap(a,b): 
     return any(i for i in a if i in b)

正如 John 和 Lie 所指出的,当两个列表 bool(i) == False 共享每个 i 时,这会给出不正确的结果。它应该是:

return any(i in b for i in a)
于 2010-07-03T02:28:26.743 回答
1

如果您不关心重叠元素可能是什么,您可以简单地检查len组合列表与组合为一组的列表。如果有重叠的元素,集合会更短:

len(set(a+b+c))==len(a+b+c) 如果没有重叠,则返回 True。

于 2015-03-10T16:11:06.403 回答
1

这个问题已经很老了,但我注意到当人们争论集合与列表时,没有人想到将它们一起使用。按照 Soravux 的例子,

列表的最坏情况:

>>> timeit('bool(set(a) & set(b))',  setup="a=list(range(10000)); b=[x+9999 for x in range(10000)]", number=100000)
100.91506409645081
>>> timeit('any(i in a for i in b)', setup="a=list(range(10000)); b=[x+9999 for x in range(10000)]", number=100000)
19.746716022491455
>>> timeit('any(i in a for i in b)', setup="a= set(range(10000)); b=[x+9999 for x in range(10000)]", number=100000)
0.092626094818115234

列表的最佳案例:

>>> timeit('bool(set(a) & set(b))',  setup="a=list(range(10000)); b=list(range(10000))", number=100000)
154.69790101051331
>>> timeit('any(i in a for i in b)', setup="a=list(range(10000)); b=list(range(10000))", number=100000)
0.082653045654296875
>>> timeit('any(i in a for i in b)', setup="a= set(range(10000)); b=list(range(10000))", number=100000)
0.08434605598449707

因此,比遍历两个列表更快的是遍历一个列表以查看它是否在一个集合中,这是有道理的,因为检查一个数字是否在一个集合中需要恒定的时间,而通过迭代一个列表进行检查所花费的时间与长度成正比名单。

因此,我的结论是遍历一个列表,并检查它是否在一个 set 中

于 2014-10-08T22:03:02.103 回答
1

我会用函数式编程风格再扔一个:

any(map(lambda x: x in a, b))

解释:

map(lambda x: x in a, b)

返回一个布尔值列表,其中的元素b位于a. 然后将该列表传递给,如果有任何元素any,它只会返回。 TrueTrue

于 2016-11-09T18:08:56.463 回答