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

Question

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

196

我想检查一个列表中是否有任何项存在于另一个列表中。我可以使用下面的代码简单地实现它，但我怀疑可能有一个库函数可以做到这一点。如果没有，是否有更适合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
   ....:

- fmark

请参考以下链接：https://dev59.com/QH3aa4cB1Zd3GeqPgKd0#44786707 - 0 _

对于numpy解决方案，请参见[python - Check if 2 arrays have at least one element in common? - Stack Overflow]（https://dev59.com/c4_ea4cB1Zd3GeqPTNCz）（尽管不清楚它是否实际上更快） - user202729

9个回答

28

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

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

- John Machin

6

最坏情况下的时间复杂度为 O(n + m)。然而，它会创建一个新的集合，并且不会在早期发现共同元素时跳出循环。 - Matthew Flaschen

1

我很好奇为什么这个算法的时间复杂度是 O(n + m)。我的猜测是集合使用哈希表实现，因此 in 运算符可以在 O(1) 时间内工作（除了退化情况）。这是正确的吗？如果是这样的话，考虑到哈希表的最坏查找性能为 O(n)，那么在最坏情况下它会有 O(n * m) 的性能吗？ - fmark

1

@fmark：从理论上讲，你是对的。但实际上，没有人会在意；读一下CPython源代码中Objects/dictobject.c文件里的注释（集合只是没有值的字典），看看能否生成一个键列表，使查询性能为O(n)。 - John Machin

好的，谢谢你澄清，我在想是否有一些神奇的事情正在发生 :)。虽然我同意实际上我不需要关心，但是生成一个会导致O(n)查找性能的键列表是微不足道的；），请参见http://pastebin.com/Kn3kAW7u 只是为了好玩。 - fmark

@fmark：没有魔法，只有工程。是的，定义一个返回常量的哈希函数很简单。哈哈笑笑。现在再试一次，不要用非标准的哈希函数。 - John Machin

2

是的，我知道。另外，我刚刚阅读了你指向我的源代码，该源代码记录了非随机哈希函数（如内置函数）中的更多魔法。我假设它需要像Java那样的随机性，这会导致像这样的怪物：https://dev59.com/iXE85IYBdhLWcg3wvGKm。我需要不断提醒自己**Python不是Java**（谢天谢地！）。 - fmark

11

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

只要在 sb 中找到 3，它就会立即返回 True。

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

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

这个代码依赖于 imap 的迭代器，其是用 C 实现的，而不是生成器表达式。它还使用 sb.__contains__ 作为映射函数。我不知道这会有多大的性能差异。它仍然可以进行短路计算。

- Matthew Flaschen

2

交集算法中的循环均为C代码；而您的方法中有一个包含Python代码的循环。最大的未知因素是空交集是可能还是不可能的。 - John Machin

2

你也可以使用 any(itertools.imap(sb.__contains__, a))，这应该是更快的，因为它避免了使用 lambda 函数。 - Dave Kirby

谢谢，@Dave。 :) 我同意去掉lambda表达式是一个胜利。 - Matthew Flaschen

6

您也可以在列表推导式中使用 any ：

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

- Ioachim

6

你可以这样做，但时间复杂度是O(nm)，而使用集合交集方法的时间复杂度是O(n+m)。你也可以不使用列表推导式（去掉“[]”），这样可以更快地运行并且使用更少的内存，但时间复杂度仍然是O(nm)。 - John Machin

1

尽管你的大 O 分析是正确的，我怀疑在 n 和 m 的小值情况下，构建底层哈希表所需的时间会起到作用。大 O 忽略了计算哈希所需的时间。 - Anthony Conyers

2

构建“哈希表”是摊销O(n)。 - John Machin

1

我明白你的意思，但你要丢弃的常数非常大。对于大的n值来说这并不重要，但对于小的n值来说就很重要了。 - Anthony Conyers

4

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

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

- Toughy

1

似乎第一个参数不一定要提供一个set或frozenset。我尝试使用字符串，它也可以工作（即：任何可迭代对象都可以）。 - Aktau

2

您可以使用带有生成器表达式的任何内置函数：

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)

- Anthony Conyers

1

放大Lie Ryan的评论：对于任何在交集中bool(x)为False的项目x，都会给出错误的结果。在Lie Ryan的例子中，x是0。唯一的修复方法是any(True for i in a if i in b)，它更好地编写为已经看到的any(i in b for i in a)。 - John Machin

1

更正：当交集中的所有项x都满足bool(x)为False时，将会得到错误的结果。 - John Machin

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

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

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

- binoche9

1

使用 @Toughy 所指示的方法，在(frozen)set上使用 isdisjoint() 方法会更好: 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.00913715362548828 - Aktau

1

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

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

- domoarigato

如果第一个值重叠，它仍然会将整个列表转换为集合，无论大小如何。 - Peter Wood

如果列表中有重复的数字怎么办？ - Anonymous

1

我将用函数式编程风格再举一个例子：

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

解释：

说明：

map(lambda x: x in a, b)

返回一个布尔值列表，其中b的元素在a中被找到。然后将该列表传递给any函数，如果任何元素为True，则该函数简单地返回True。

- cs01

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Soravux · Accepted Answer

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

测试两个列表 a 和 b 是否有任何相同的元素，通常有四种常见的方法。第一种方法是将它们都转换成集合并检查它们的交集，例如：

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

因为在Python中，集合使用哈希表存储，因此搜索它们的时间复杂度是 O(1)（有关Python运算符复杂度的更多信息，请参见此处）。理论上，对于列表中的n和m对象，平均情况下的时间复杂度为O(n+m)。但是：

必须首先将列表转换为集合，这可能需要一定的时间。
假设您的数据中哈希碰撞很少。

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

any(i in a for i in b)

这样可以进行就地搜索，因此不会为中间变量分配新的内存。它还会在第一次查找失败时退出。但是，在列表上in运算符始终是O(n)（请参见此处）。

另一个提议的选项是混合方案，通过迭代其中一个列表，将另一个列表转换为集合并在该集合上测试成员资格，如下所示：

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

第四种方法是利用(frozen)sets的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次重复，而不是之前的10万次。当没有元素共享时，此设置也很好地近似，并且是不相交和集合交集方法的最佳情况。

以下是两个使用随机数进行分析（而不是偏向某种技术的设置）：

高共享几率：从[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()方法是最佳选择，因为当没有元素共享时，生成器表达式效率很低，执行时间会很长。