6

重み付けされていない大規模な循環グラフであるデータ セットがあります。サイクルは、約 5 ～ 6 パスのループで発生します。約 8000 のノードで構成され、各ノードには 1 ～ 6 (通常は約 4 ～ 5) の接続があります。私は単一ペアの最短経路計算を行っており、次のコードを実装して幅優先検索を実行しています。

from Queue import Queue

q = Queue()
parent = {}
fromNode = 'E1123'
toNode = 'A3455'

# path finding
q.put(fromNode)
parent[fromNode] = 'Root'

while not q.empty():
  # get the next node and add its neighbours to queue
  current = q.get()
  for i in getNeighbours(current):
    # note parent and only continue if not already visited
    if i[0] not in parent:
      parent[i[0]] = current
      q.put(i[0])

  # check if destination
  if current == toNode:
    print 'arrived at', toNode
    break

上記のコードは Python 2.6 Queue モジュールを使用しています。SQL 呼び出しは高速です。

コードは正常に動作しますが、約 7 層の深さまでテストを実行するには約 20 秒かかります (2.5GHz Intel 4GB RAM OS X 10.6)。

このコードの実行時間を改善する方法についてのコメントを歓迎します。

4

4 に答える 4

11

さて、コメントに賛成票を投じたので、今すぐ回答にします。

タイト ループ内の SQL は間違いなく速度を落としています。通話の速さは気にしません。考えてみてください。クエリを解析し、ルックアップを実行するように要求しているのですが、それと同じくらい高速ですが、まだタイト ループになっています。データセットはどのように見えますか? データセット全体をメモリに入れることができますかSELECT、または少なくとも MySQL の外で作業できますか?

そのデータをメモリ内で処理すると、パフォーマンスが大幅に向上します。

于 2009-11-18T02:44:36.197 に答える
1

このようなもの：

#!/usr/bin/env python

from Queue import Queue

def traverse_path(fromNode, toNode, nodes):
    def getNeighbours(current, nodes):
        return nodes[current] if current in nodes else []

    def make_path(toNode, graph):
        result = []
        while 'Root' != toNode:
            result.append(toNode)
            toNode = graph[toNode]
        result.reverse()
        return result

    q = Queue()
    q.put(fromNode)
    graph = {fromNode: 'Root'}

    while not q.empty():
        # get the next node and add its neighbours to queue
        current = q.get()
        for neighbor in getNeighbours(current, nodes):
            # use neighbor only continue if not already visited
            if neighbor not in graph:
                graph[neighbor] = current
                q.put(neighbor)

        # check if destination
        if current == toNode:
            return make_path(toNode, graph)
    return []

if __name__ == '__main__':
    nodes = {
        'E1123': ['D111', 'D222', 'D333', 'D444'],
        'D111': ['C01', 'C02', 'C04'],
        'D222': ['C11', 'C03', 'C05'],
        'D333': ['C01'],
        'C02': ['B1'],
        'B1': ['A3455']
    }
    result = traverse_path('E1123', 'A3455', nodes)
    print result

['E1123', 'D111', 'C02', 'B1', 'A3455']

SQL クエリをリストの辞書に置き換えると (これは難しい部分です)、このパフォーマンスが得られます。

于 2009-11-18T04:03:00.843 に答える
0

そのマシンには複数のコアがあるに違いありませんね。並行して実行します。

Python スレッディング

于 2009-11-18T02:37:53.440 に答える
0

うーん、BFS では、既に見たノードにマークを付けて、二度とアクセスしないようにする必要はありませんか?

于 2009-11-18T02:38:13.077 に答える