测试列表是否共享 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
....:
132815 次浏览
小开 
def lists_overlap3(a, b):
return bool(set(a) & set(b))

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

小开

你也可以使用列表内涵:

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

你可以使用任何内置的函数/w 生成器表达式:

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)
小开 
def lists_overlap(a, b):
sb = set(b)
return any(el in sb for el in a)

这是渐近最优的(最坏情况 O (n + m)) ，并且可能比交叉方法更好，因为 any的短路。

例如:

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

一到 3 in sb就会返回 True

编辑: 另一个变化(感谢 Dave Kirby) :

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

这依赖于用 C 实现的 imap迭代器，而不是生成器理解。它还使用 sb.__contains__作为映射函数。我不知道这对性能有多大影响。还是会短路。

小开

在 python 2.6或更高版本中，您可以:

return not frozenset(a).isdisjoint(frozenset(b))
小开
最佳答案

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

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

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

因为 集合使用 Python 中的哈希表存储，搜索它们是 O(1)(有关 Python 中运算符复杂性的更多信息，请参见 给你)。理论上，对于列表 a和 b中的 n和 m对象，平均值为 O(n+m)。但是

  1. 它必须首先从列表中创建集合，这可能需要花费不可忽视的时间，并且
  2. 它假设散列冲突在您的数据中是稀疏的。

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

any(i in a for i in b)

这允许就地搜索，因此不会为中间变量分配新的内存。它也会在第一次发现时退出。但是在列表中，ABC0操作符始终是 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

下面是这个例子的执行时间的图表，它是列表大小的函数:

Element sharing test execution time when shared at the beginning

注意，两个轴都是对数的。这表示生成器表达式的最佳情况。可以看出，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

Element sharing test execution time when shared at the end

值得注意的是，对于较大的列表大小，生成器表达式要慢得多。这只是1000次重复，而不是上一个数字的100000次。当没有共享元素时，这种设置也非常接近，是不相交和集合交方法的最佳情况。

下面是两个使用随机数的分析(而不是操纵设置来支持一种或另一种技术) :

Element sharing test execution time for randomly generated data with high chance of sharing Element sharing test execution time for randomly generated data with high chance of sharing

共享概率高: 元素是从 [1, 2*len(a)]中随机抽取的。共享概率低: 元素是从 [1, 1000*len(a)]中随机抽取的。

到目前为止，这个分析假设两个列表的大小是相同的。对于两个不同大小的列表，例如 a要小得多，isdisjoint()总是更快:

Element sharing test execution time on two differently sized lists when shared at the beginning Element sharing test execution time on two differently sized lists when shared at the end

确保 a列表较小，否则性能会降低。在这个实验中，将 a列表大小设置为 5常数。

总之:

  • 如果列表非常小(< 10个元素) ，则 not set(a).isdisjoint(b)总是最快的。
  • 如果列表中的元素已排序或具有可以利用的正则结构，则生成器表达式 any(i in a for i in b)在大列表大小上是最快的;
  • 用 not set(a).isdisjoint(b)测试集合的交集，not set(a).isdisjoint(b)总是比 bool(set(a) & set(b))快。
  • 混合的“通过列表迭代，在集合上测试”a = set(a); any(i in a for i in b)通常比其他方法慢。
  • 当涉及到不共享元素的列表时，生成器表达式和混合方法要比其他两种方法慢得多。

在大多数情况下，使用 isdisjoint()方法是最好的方法，因为生成器表达式的执行时间要长得多，因为当没有共享元素时，它的效率非常低。

小开

这个问题很老了，但是我注意到当人们在讨论集合和列表的时候，没有人想到把它们放在一起使用。以索拉维为例,

列表最糟糕的情况:

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

因此，比迭代两个列表更快的方法是迭代一个列表来查看它是否在一个集合中，这是有意义的，因为检查一个数字是否在一个集合中需要固定的时间，而通过迭代一个列表来检查花费的时间与列表的长度成正比。

因此，我的结论是 迭代一个列表，并检查它是否在一个集合中。

小开

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

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

小开

我将引入另一个函数式编程风格的例子:

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

说明:

map(lambda x: x in a, b)

返回在 a中找到 b元素的布尔值列表。然后，该列表被传递给 any，如果有任何元素是 True，它只返回 True。


提交答案