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

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)。）

Answer 2

您不能在未排序的dict上运行简单的线性搜索并期望它很快（至少不是很快）。 有这么多的算法，可以帮助您解决这个问题，在一个非常优化的方式。你知道吗

建议的R-Tree是存储位置的完美数据结构。你知道吗

你也可以在这个维基百科页面上寻找解决方案：Nearest Neighbor Search

Answer 3

每次运行此函数时，您都在创建和销毁一个字典（distances），其中包含一百万项，但这甚至不是必需的。试试这个：

def node_closest_to_location_in_space(location_in_space)
    global node_location_by_nodeId
    closest_node = None
    closest_distance = 1e100  # An arbitrary, HUGE, value
    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
    return (closest_node, closest_distance)

我相信每次调用函数时创建和删除distancesdict所涉及的开销是影响性能的因素。如果是这样，这个版本应该更快。你知道吗