Skip to main content
 首页 » 编程设计

python之用于收集 numpy 数组的高效查找表

2025年05月04日13wuhuacong

我想知道在 Python 中为 float (和 float 集合)创建查找表的最有效方法是什么。由于 set 和 dicts 都需要键是可散列的,我想不能使用某种接近度来检查与已插入的接近度,可以吗?我看过this answer这并不是我想要的,因为我不想给用户创建正确 key 的负担,而且我还需要将其扩展为 float 集合。 例如,给定以下代码:

>>> import numpy as np 
>>> a = {np.array([0.01, 0.005]): 1} 
Traceback (most recent call last): 
  File "<stdin>", line 1, in <module> 
TypeError: unhashable type: 'numpy.ndarray' 
>>> a = {tuple(np.array([0.01, 0.005])): 1} 
>>> tuple(np.array([0.0100000000000001,0.0050002])) in a 
False 

我希望最后一条语句返回 True。来自 C++ 世界,我会创建一个 std::map 并提供一个比较函数,该函数可以与一些用户定义的公差进行比较,以检查值是否已添加到数据结构中。当然,这个问题很自然地延伸到数组的查找表(例如 numpy 数组)。那么,实现我所寻找的目标的最有效方法是什么?

请您参考如下方法:

既然您对 3D 点感兴趣,您可以考虑使用一些为存储空间数据而优化的数据结构,例如 KD-tree .这是 available在 Scipy 中并允许查找最接近给定坐标的点。在您查看了这个点之后,您可以检查一下您是否在一定的容差范围内接受新点。

用法应该是这样的(未经测试,我自己从未使用过):

from scipy.spatial import KDTree 
points = ... # points is [Nx3] 
tree = KDTree(points)   
new_point = ... # array of length 3 
distance, nearest_index = tree.query(new_point) 
if distance > tolerance:  # add point 
    points = np.vstack((points, new_point)) 
    tree = KDTree(points)  # generate tree from scratch 

请注意,KD 树可以有效地在静态点集合中查找点(查找成本为 O(log(N)),但它们并未针对重复优化添加新点。Scipy实现甚至缺少添加新点的方法,因此每次插入新点都必须生成一棵新树。由于此操作可能是O(N*log(N)),仅对所有距离进行暴力计算可能会更快,这会花费 O(N)。另请注意,还有一个替代版本 cKDTree ,它可能会被实现在 C 中为了速度,文档对此并不清楚。