测试列表是否共享python中的任何项目

Question

我想检查一个列表中的任何项目是否存在于另一个列表中。我可以使用下面的代码简单地做到这一点，但是我怀疑可能有一个库函数可以做到这一点。如果没有，是否有更多的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]: FalseIn [83]: lists_overlap(a, c)Out[83]: TrueIn [84]: def lists_overlap2(a, b):   ....:     return len(set(a).intersection(set(b))) > 0   ....: 

Answer 1

简短答案：使用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()（冻结）集的方法（请参阅此处），例如：

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

Answer 2

def lists_overlap3(a, b):

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

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