概述
我有一个数据集,这是一个大的未加权循环图.循环发生在约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调用,并将邻居作为元组列表返回,例如： (( ‘富’,),( ‘巴’,)). sql调用很快.
代码工作正常但是测试到大约7层的深度需要大约20秒才能运行(2.5GHz Intel 4GB RAM OS X 10.6)
紧密循环中的sql肯定会让你失望.我不在乎通话速度有多快.想一想 – 你要求解析一个查询,运行一个查询 – 尽可能快,它仍然处于紧密循环中.你的数据集是什么样的？您是否可以将整个数据集选择到内存中,或者至少在MysqL之外使用它？
如果您在内存中使用该数据,您将看到显着的性能提升.
总结
以上是编程之家为你收集整理的python – 这种广度优先搜索能否更快？全部内容，希望文章能够帮你解决python – 这种广度优先搜索能否更快？所遇到的程序开发问题。
如果您也喜欢它,动动您的小指点个赞吧
602392714
清零编程群