检查列表中是否存在值的最快方法

检查一个值是否存在于一个非常大的列表的最快方法是什么?

当前回答

你可以把你的物品放在一个集合里。设置查找非常有效。

Try:

s = set(a)
if 7 in s:
  # do stuff

在注释中，你说你想获取元素的索引。不幸的是，集合没有元素位置的概念。另一种方法是对列表进行预先排序，然后在每次需要查找元素时使用二分搜索。

其他回答

请注意，in操作符不仅测试相等性(==)，还测试恒等式(is)，列表的in逻辑大致相当于以下内容(实际上是用C而不是Python编写的，至少在CPython中是这样):

对于s中的元素: 如果元素是目标: #快速检查身份意味着相等还真如果element == target: #慢速检查实际相等还真返回假

在大多数情况下，这个细节是无关紧要的，但在某些情况下，它可能会让Python新手感到惊讶，例如numpy。NAN具有不等于自身的不寻常性质:

>>> import numpy
>>> numpy.NAN == numpy.NAN
False
>>> numpy.NAN is numpy.NAN
True
>>> numpy.NAN in [numpy.NAN]
True

为了区分这些不寻常的情况，你可以使用任何()，比如:

>>> lst = [numpy.NAN, 1 , 2]
>>> any(element == numpy.NAN for element in lst)
False
>>> any(element is numpy.NAN for element in lst)
True

注意，使用any()的列表的in逻辑将是:

any(element is target or element == target for element in lst)

然而，我应该强调这是一个边缘情况，对于绝大多数情况，in操作符是高度优化的，当然正是你想要的(无论是对列表还是对集合)。

听起来您的应用程序可能会从使用Bloom Filter数据结构中获得优势。

简而言之，bloom过滤器查找可以非常快速地告诉你一个值是否绝对不存在于一个集合中。否则，您可以执行较慢的查找，以获得可能在列表中的值的索引。因此，如果您的应用程序倾向于获得“未找到”结果，而不是“找到”结果，您可能会通过添加Bloom Filter看到速度的提高。

关于细节，维基百科提供了Bloom过滤器如何工作的很好的概述，在网上搜索“python Bloom过滤器库”将提供至少两个有用的实现。

def check_availability(element, collection: iter):
    return element in collection

使用

check_availability('a', [1,2,3,4,'a','b','c'])

我相信这是知道所选值是否在数组中的最快方法。

你可以把你的物品放在一个集合里。设置查找非常有效。

Try:

s = set(a)
if 7 in s:
  # do stuff

7 in a

最清晰最快的方法。

您也可以考虑使用一个集合，但是从列表中构造该集合所花费的时间可能比快速成员测试所节省的时间要多。唯一确定的方法就是做好基准测试。(这也取决于你需要什么操作)

推荐文章