1

一連の場所と 1 つの場所が与えられた場合、その場所に最も近い場所をセットから見つけます。ノードを通るパスを見つけることではありません。鳥瞰図での距離です。

位置は「ノード」のプロパティです (有限要素ソフトウェア拡張用です)。問題は次のとおりです。これには長い時間がかかります。私はもっ​​と速いものを探しています。1 人のユーザーは、100 万の場所のセット (セットは同じまま) に対して、この関数を (別の 1 つの場所で) 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
4

3 に答える 3

1

ソートされていない辞書で単純な線形検索を実行して、高速であると期待することはできません (少なくともそれほど高速ではありません)。最適化された方法でこの問題に取り組むのに役立つ非常に多くのアルゴリズムがあります。

提案されているR ツリーは、場所を保存するのに最適なデータ構造です。

このウィキペディアのページで解決策を探すこともできます: Nearest Neighbor Search

于 2013-06-07T09:29:37.763 に答える
0

location 引数へのインデックス作成には時間がかかり、場所は 100 万個のすべてのノードで変更されないため、これらの不変条件を 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。これは高速な 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は 2D 距離計算のみを行うように書かれているため、3D を行うには を呼び出す必要がありますhypot(hypot(xdist,ydist),zdist)。)

于 2013-06-07T12:11:38.117 に答える
0

distancesこの関数を実行するたびに、100 万個のアイテムを含む辞書 ( ) を作成および破棄していますが、その必要さえありません。これを試して：

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)

distances関数を呼び出すたびにそのdictを作成および破棄することに伴うオーバーヘッドが、パフォーマンスを低下させていたと思います。もしそうなら、このバージョンはより速いはずです。

于 2013-06-07T08:52:32.883 に答える