Czy to pierwsze wyszukanie może być szybsze?
Mam zestaw danych, który jest dużym nieważonym wykresem cyklicznym. Cykle występują w pętlach około 5-6 ścieżek. Składa się z około 8000 węzłów, a każdy węzeł ma od 1-6 (zwykle około 4-5) połączeń. Wykonuję obliczenia najkrótszej ścieżki pojedynczej pary i zaimplementowałem następujący kod, aby przeprowadzić pierwsze wyszukiwanie.
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
Powyższy kod używa modułu kolejki Python 2.6, a getNeighbours () jest po prostu procedurą, która wykonuje pojedyncze wywołanie MySQL i zwraca sąsiadów jako listę krotek, np. (('foo',), ('bar',)). Wywołanie SQL jest szybkie.
Kod działa dobrze, jednak testowanie do głębokości około 7 warstw trwa około 20 sekund (2,5 GHz Intel 4 GB RAM X 10.6)
Z zadowoleniem przyjmuję wszelkie uwagi na temat poprawy czasu działania tego kodu.