Kann diese Breitensuche schneller gemacht werden?

Question

Ich habe einen Datensatz, der ein großer ungewichteter zyklischer Graph ist. Die Zyklen treten in Schleifen von ungefähr 5-6 Pfaden auf. Es besteht aus ungefähr 8000 Knoten und jeder Knoten hat 1-6 (normalerweise 4-5) Verbindungen. Ich mache Single Pair Shortest Path-Berechnungen und habe den folgenden Code implementiert, um eine Breitensuche durchzuführen.

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 

Der obige Code verwendet die Python 2.6 Queue-Modul und getNeighbours() ist einfach eine Unterroutine, die einen einzelnen MySQL Anruf tätigt und gibt die Nachbarn als eine Liste von Tupeln z.B. (('foo',), ('bar',)). Der SQL-Aufruf ist schnell.

Der Code funktioniert ok Prüfung jedoch nach unten von etwa 7 Schichten bis in Tiefen dauert etwa 20 Sekunden (2,5 GHz Intel 4GB RAM OS X 10.6)

Ich würde

laufen begrüßen alle Kommentare darüber, wie den Lauf zu verbessern Zeit dieses Codes.

Answer 1

Nun, angesichts der Upvotes auf den Kommentar, werde ich es jetzt eine Antwort machen.

Die SQL in der engen Schleife ist definitiv verlangsamt Sie. Es ist mir egal, wie schnell der Anruf ist. Denken Sie darüber nach - Sie verlangen, dass eine Abfrage geparst wird, eine Suche ausgeführt wird - so schnell wie das ist, ist es immer noch in einer engen Schleife. Wie sieht Ihr Datensatz aus? Kannst du einfach SELECT den gesamten Datensatz in den Speicher schreiben, oder zumindest damit außerhalb von MySQL arbeiten?

Wenn Sie mit diesen Daten im Speicher arbeiten, werden Sie eine deutliche Leistungssteigerung feststellen.

Answer 2

Ich wette, dass die Maschine mehr als einen Kern hat, oder? Führen Sie es parallel aus.

Python Threading

Answer 3

Hmm, beinhaltet keine BFS Markierung Knoten Sie bereits gesehen haben, so dass Sie sie nicht wieder besuchen?

Answer 4

Etwas wie folgt aus:

#!/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'] 

Wenn Sie Ihre SQL-Abfragen mit einem Wörterbuch von Listen ersetzen (und das wäre der schwierige Teil sein), werden Sie diese Leistung erzielen.