检查一个值是否存在于一个非常大的列表的最快方法是什么?
当前回答
听起来您的应用程序可能会从使用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'])
我相信这是知道所选值是否在数组中的最快方法。
空间数据的边缘情况
可能有更快的算法来处理空间数据(例如重构以使用k-d树)，但检查向量是否在数组中的特殊情况是有用的:
如果你有空间数据(即笛卡尔坐标) 如果你有整数掩码(即数组过滤)
在这种情况下，我想知道由两点定义的(无向)边是否在(无向)边的集合中，这样
(pair in unique_pairs) | (pair[::-1] in unique_pairs) for pair in pairs
其中pair构成两个任意长度的向量(即形状(2,N))。
如果这些向量之间的距离是有意义的，那么检验可以用一个浮点不等式来表示
test_result = Norm(v1 - v2) < Tol
和“值存在于列表”是简单的任何(test_result)。
下面是整数对和R3向量对的示例代码和虚拟测试集生成器。
# 3rd party
import numpy as np
import numpy.linalg as LA
import matplotlib.pyplot as plt
# optional
try:
from tqdm import tqdm
except ModuleNotFoundError:
def tqdm(X, *args, **kwargs):
return X
print('tqdm not found. tqdm is a handy progress bar module.')
def get_float_r3_pairs(size):
""" generate dummy vector pairs in R3 (i.e. case of spatial data) """
coordinates = np.random.random(size=(size, 3))
pairs = []
for b in coordinates:
for a in coordinates:
pairs.append((a,b))
pairs = np.asarray(pairs)
return pairs
def get_int_pairs(size):
""" generate dummy integer pairs (i.e. case of array masking) """
coordinates = np.random.randint(0, size, size)
pairs = []
for b in coordinates:
for a in coordinates:
pairs.append((a,b))
pairs = np.asarray(pairs)
return pairs
def float_tol_pair_in_pairs(pair:np.ndarray, pairs:np.ndarray) -> np.ndarray:
"""
True if abs(a0 - b0) <= tol & abs(a1 - b1) <= tol for (ai1, aj2), (bi1, bj2)
in [(a01, a02), ... (aik, ajl)]
NB this is expected to be called in iteration so no sanitization is performed.
Parameters
----------
pair : np.ndarray
pair of vectors with shape (2, M)
pairs : np.ndarray
collection of vector pairs with shape (N, 2, M)
Returns
-------
np.ndarray
(pair in pairs) | (pair[::-1] in pairs).
"""
m1 = np.sum( abs(LA.norm(pairs - pair, axis=2)) <= (1e-03, 1e-03), axis=1 ) == 2
m2 = np.sum( abs(LA.norm(pairs - pair[::-1], axis=2)) <= (1e-03, 1e-03), axis=1 ) == 2
return m1 | m2
def get_unique_pairs(pairs:np.ndarray) -> np.ndarray:
"""
apply float_tol_pair_in_pairs for pair in pairs
Parameters
----------
pairs : np.ndarray
collection of vector pairs with shape (N, 2, M)
Returns
-------
np.ndarray
pair if not ((pair in rv) | (pair[::-1] in rv)) for pair in pairs
"""
pairs = np.asarray(pairs).reshape((len(pairs), 2, -1))
rv = [pairs[0]]
for pair in tqdm(pairs[1:], desc='finding unique pairs...'):
if not any(float_tol_pair_in_pairs(pair, rv)):
rv.append(pair)
return np.array(rv)
请注意，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操作符是高度优化的，当然正是你想要的(无论是对列表还是对集合)。
如果您只想检查列表中是否存在一个元素，
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 a
最清晰最快的方法。
您也可以考虑使用一个集合，但是从列表中构造该集合所花费的时间可能比快速成员测试所节省的时间要多。唯一确定的方法就是做好基准测试。(这也取决于你需要什么操作)
