这种广度优先搜索能否更快？

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 RAM OS X 10.6)

我欢迎任何关于如何改善此代码的运行时间的意见.

Answer 1

好吧,考虑到评论的赞成,我现在就回答它.

紧密循环中的SQL 肯定会让你失望.我不在乎通话速度有多快.想一想 - 你要求解析一个查询,运行一个查询 - 尽可能快,它仍然处于紧密循环中.你的数据集是什么样的？你能将SELECT整个数据集合到内存中,还是至少在MySQL之外使用它？

如果您在内存中使用该数据,您将看到显着的性能提升.