这个广度优先搜索可以更快吗？

Question

我有一个数据集，它是一个大型的无权循环图。这个图里有一些循环，大约有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模块，而getNeighbours()只是一个子程序，它会进行一次MySQL的调用，并返回邻居节点，结果是一个元组列表，比如说 (('foo',),('bar',))。这个SQL调用的速度很快。

代码运行得还不错，不过测试到大约7层深度时，运行大约需要20秒（我的电脑是2.5GHz的Intel处理器，4GB内存，操作系统是OS X 10.6）。

我希望能得到一些关于如何提高这段代码运行速度的建议。

Answer 1

我敢打赌那台机器有不止一个核心，对吧？那就让它并行运行吧。

Python 线程

Answer 2

像这样：

#!/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查询换成一个包含列表的字典（这部分会比较复杂），你就能获得这样的性能。

Answer 3

好吧，看到评论有这么多赞，我就把它变成一个回答吧。

在紧密循环中执行的SQL查询绝对会拖慢你的速度。我不在乎这个调用有多快。想想看——你在请求一个查询被解析，还要进行查找——无论这个过程多快，它还是在一个紧密的循环里。你的数据集是什么样的？你能不能把整个数据集用SELECT语句加载到内存中，或者至少在MySQL之外处理它？

如果你在内存中处理这些数据，你会看到明显的性能提升。