グラフを最適化してパスを特定し、特定の座標でノードを取得する

Question

私はdictとして表されるグラフクラスを構築しています。グラフクラスは、大きな2Dグリッドマトリックス上でパスを見つけるのに使用されます。ノードはキーとして格納され、隣接ノードは値として格納されます。

これは高速パス検索には効果的ですが、x座標とy座標で決まる特定のノードを特定する必要があります。

class Node(object): 
    def __init__(self, x, y): 
     self.x = x 
     self.y = y 

class Graph(dict): 
    def get_node_at(self, x, y): 
     for node in self: 
      if node.x == x and node.y == y: 
       return node 

    def set_neighbours(self): 
     pass 

graph = Graph() 

# build a 2d matrix of nodes 
for x in range(10): 
    for y in range(10): 
     graph[Node(x,y)] = [] 

# set the neighbour nodes for each node 
graph.set_neighbours() 
mynode = graph.get_node_at(6,6) # will later be executed quite often 

get_node_at方法は、大規模なグリッド上に良好に機能するように、グラフのクラスを最適化する方法はありますか？

Answer 1

Graphにインデックスを追加すると{(x,y):node}のようになります。インデックスにNodeを追加するには__setitem__を実装する必要があり、Nodeが既に存在する場合はそれを削除し、__delitem__もインデックスからNodeを削除します。これによりget_node_at(self, x, y)はちょうどreturn self.index[(x,y)]になります。