在 Python 中测试列表是否共享任何项目

问题描述：

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

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
   ....: 

解决方案 1：

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

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

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

因为集合在 Python 中是使用哈希表存储的，所以搜索它们是O(1)（有关 Python 中运算符复杂性的更多信息，请参阅此处）。从理论上讲，对于列表和中的和对象，这是O(n+m)平均水平。但是n`mab`

1. 它必须首先从列表中创建集合，这可能需要花费大量时间，并且

2. 它假设您的数据中的散列冲突是稀疏的。

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

any(i in a for i in b)

这允许就地搜索，因此不会为中间变量分配新内存。它还会在第一次找到时退出。但in运算符始终O(n)在列表中（参见此处）。

另一个建议的选项是混合迭代其中一个列表，将另一个列表转换为集合并测试该集合的成员身份，如下所示：

a = set(a); any(i in a for i in b)

第四种方法是利用isdisjoint()（冻结）集合的方法（参见此处），例如：

not set(a).isdisjoint(b)

如果搜索的元素靠近数组的开头（例如，它已排序），则生成器表达式是首选，因为集合交集方法必须为中间变量分配新内存：

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

解决方案 2：

def lists_overlap3(a, b):
    return bool(set(a) & set(b))

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

解决方案 3：

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

编辑：另一种变化（感谢 Dave Kirby）：

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

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

解决方案 4：

您还可以使用any列表理解：

any([item in a for item in b])

解决方案 5：

在 Python 2.6 或更高版本中你可以执行以下操作：

return not frozenset(a).isdisjoint(frozenset(b))

解决方案 6：

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

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

正如 John 和 Lie 指出的那样，当两个列表共享的每个 i bool(i) == False 时，这会产生不正确的结果。应该是：

return any(i in b for i in a)

解决方案 7：

这个问题相当老了，但我注意到，当人们争论集合与列表时，没有人想到将它们一起使用。按照 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

因此，比遍历两个列表更快的是通过遍历一个列表来查看它是否在一个集合中，这是有道理的，因为检查一个数字是否在一个集合中需要恒定的时间，而通过遍历列表来检查所需的时间与列表的长度成比例。

因此，我的结论是遍历列表，并检查它是否在集合中。

解决方案 8：

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

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

解决方案 9：

我将再举一个具有函数式编程风格的事例：

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

解释：

map(lambda x: x in a, b)

b返回在中找到元素的布尔列表a。然后将该列表传递给，如果有任何元素 ，any则简单地返回。 True`True`