给定一组位置和一个位置，找到从该集到目标的最近位置

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

索引到location参数需要时间，而且对于所有一百万个节点，位置不会改变，所以请将这些不变量从for循环中取出：

for NodeId, NodeLocation in node_location_by_nodeId.iteritems():
    distance = (NodeLocation[0] - location_in_space[0])**2 + 
               (NodeLocation[1] - location_in_space[1])**2 + 
               (NodeLocation[2] - location_in_space[2])**2
    if distance <= closest_distance:
        closest_distance = distance
        closest_node = NodeId

变成：

x,y,z = location_in_space
for NodeId, NodeLocation in node_location_by_nodeId.iteritems():
    distance = (NodeLocation[0] - x)**2 + 
               (NodeLocation[1] - y)**2 + 
               (NodeLocation[2] - z)**2
    if distance <= closest_distance:
        closest_distance = distance
        closest_node = NodeId

现在它们变成了简单（更快）的本地值引用。你知道吗

您还可以尝试用对math.hypot的调用来替换距离计算，这是用fast C代码实现的：

from math import hypot

x,y,z = location_in_space
for NodeId, NodeLocation in node_location_by_nodeId.iteritems():
    distance = hypot(hypot((NodeLocation[0] - x), (NodeLocation[1] - y)),(NodeLocation[2] - z))
    if distance <= closest_distance:
        closest_distance = distance
        closest_node = NodeId

（hypot只用于进行二维距离计算，因此要进行三维计算，必须调用hypot(hypot(xdist,ydist),zdist)。）