测试列表是否共享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]: 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
   ....: 

Answer 1

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

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

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

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

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

any(i in a for i in b)

这允许就地搜索,因此不为中间变量分配新内存.它还拯救了第一个发现.但是in运营商总是O(n)在列表上(见这里).

另一个提议的选项是hybrid来迭代列表中的一个,转换集合中的另一个并测试该集合的成员资格,如下所示:

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

Answer 3

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

一旦到达,它将立即返回True 3 in sb

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

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

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

Answer 4

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

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