python - 给定一组位置和一个位置，找到该组位置与单个位置最接近的位置

Question

给定一组位置和一个位置，从该组位置中找到最接近该单个位置的位置。它不是寻找通过节点的路径；而是寻找通过节点的路径。这是关于鸟瞰距离。

位置是“节点”的属性(用于有限元软件扩展)。问题是:这需要很长时间。我正在寻找更快的东西。一个用户必须在一组 100 万个位置(该组保持不变)上调用此函数最多 500 次(使用不同的单个位置)。

我宁愿在进行此计算之前不限制集合；我不必查询数据库或任何东西；我觉得这个简单的算术无论如何应该在几毫秒内完成。我不明白为什么要花这么长时间。

# excerpt of how LocationByNodeId looks like. 40k keys is a small model, can contain up to a million keys.
node_location_by_nodeId = {43815: (3.2835714285714266, -1.8875000000000068, 0.23571428571420952), 43816: (3.227857142857142, -1.8875000000000068, 0.23571428571421035)}
location_in_space=(1,3,7)

def node_closest_to_location_in_space(location_in_space):
    global node_location_by_nodeId
    distances = {}
    for NodeId in node_location_by_nodeId:
        NodeLocation = node_location_by_nodeId[NodeId]
        distances[NodeId] = (NodeLocation[0] - location_in_space[0])**2 + 
                            (NodeLocation[1] - location_in_space[1])**2 + 
                            (NodeLocation[2] - location_in_space[2])**2
    return min(distances, key=distances.get) # I don't really get this statement, i got it from here. Maybe this one is slow?

node_closest_to_location_in_space(location_in_space)

编辑:取自以下答案的解决方案将大数据集中的运行时间减少到原始运行时间的 35%(120 万次调用中的 400 次调用)。

closest_node = None
closest_distance = 1e100  # An arbitrary, HUGE, value
x,y,z = location_in_space[:3]
for NodeId, NodeLocation in LocationByNodeId.iteritems():
    distance = (NodeLocation[0] - x)**2 + (NodeLocation[1] - y)**2 + (NodeLocation[2] - z)**2
    if distance < closest_distance:
        closest_distance = distance
        closest_node = NodeId
return closest_node

Answer 1

您不能对未排序的字典运行简单的线性搜索并期望它很快(至少不是很快)。有很多算法可以帮助您以优化的方式解决这个问题。

安R-Tree正如所建议的那样，这是存储您的位置的完美数据结构。

您还可以在此维基百科页面中查找解决方案:Nearest Neighbor Search