检查一个值是否存在于一个非常大的列表的最快方法是什么?
当前回答
如果您只想检查列表中是否存在一个元素,
7 in list_data
是最快的解决方案。请注意
7 in set_data
是一个近乎自由的操作,与集合的大小无关!从一个大列表中创建一个set要比在列表中慢300到400倍,所以如果您需要检查许多元素,首先创建一个set会更快。
用perfplot创建的Plot:
import perfplot
import numpy as np
def setup(n):
data = np.arange(n)
np.random.shuffle(data)
return data, set(data)
def list_in(data):
return 7 in data[0]
def create_set_from_list(data):
return set(data[0])
def set_in(data):
return 7 in data[1]
b = perfplot.bench(
setup=setup,
kernels=[list_in, set_in, create_set_from_list],
n_range=[2 ** k for k in range(24)],
xlabel="len(data)",
equality_check=None,
)
b.save("out.png")
b.show()
其他回答
如果您只想检查列表中是否存在一个元素,
7 in list_data
是最快的解决方案。请注意
7 in set_data
是一个近乎自由的操作,与集合的大小无关!从一个大列表中创建一个set要比在列表中慢300到400倍,所以如果您需要检查许多元素,首先创建一个set会更快。
用perfplot创建的Plot:
import perfplot
import numpy as np
def setup(n):
data = np.arange(n)
np.random.shuffle(data)
return data, set(data)
def list_in(data):
return 7 in data[0]
def create_set_from_list(data):
return set(data[0])
def set_in(data):
return 7 in data[1]
b = perfplot.bench(
setup=setup,
kernels=[list_in, set_in, create_set_from_list],
n_range=[2 ** k for k in range(24)],
xlabel="len(data)",
equality_check=None,
)
b.save("out.png")
b.show()
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
在注释中,你说你想获取元素的索引。不幸的是,集合没有元素位置的概念。另一种方法是对列表进行预先排序,然后在每次需要查找元素时使用二分搜索。
听起来您的应用程序可能会从使用Bloom Filter数据结构中获得优势。
简而言之,bloom过滤器查找可以非常快速地告诉你一个值是否绝对不存在于一个集合中。否则,您可以执行较慢的查找,以获得可能在列表中的值的索引。因此,如果您的应用程序倾向于获得“未找到”结果,而不是“找到”结果,您可能会通过添加Bloom Filter看到速度的提高。
关于细节,维基百科提供了Bloom过滤器如何工作的很好的概述,在网上搜索“python Bloom过滤器库”将提供至少两个有用的实现。
7 in a
最清晰最快的方法。
您也可以考虑使用一个集合,但是从列表中构造该集合所花费的时间可能比快速成员测试所节省的时间要多。唯一确定的方法就是做好基准测试。(这也取决于你需要什么操作)