Kann diese Breitensuche schneller gemacht werden?

Question

Ich habe einen Datensatz, der eine große ungewichteten cyclisch ist Graph, der die Zyklen auftreten, in Schleifen von etwa 5-6 Pfade. Es besteht aus etwa 8000-Knoten und jeder Knoten 1-6 (in der Regel etwa 4-5) Verbindungen. Ich mache einziges Paar kürzesten Weg Berechnungen und haben den folgenden Code implementiert, um eine Breitensuche zu tun.

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 jedoch in Ordnung, nach unten testet bis zu einer Tiefe von etwa 7 Schichten dauert etwa 20 Sekunden zu laufen (2,5 GHz Intel 4GB RAM OS X 10.6)

Ich würde begrüßen alle Kommentare darüber, wie die Laufzeit dieses Codes zu verbessern.

Answer 1

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

Die SQL in der engen Schleife ist auf jeden Fall Verlangsamung Sie unten. Mir ist egal, wie schnell der Ruf ist. Denken Sie darüber nach - Sie für eine Abfrage sind gefragt analysiert werden, eine Lookup ausgeführt werden soll - so schnell wie das heißt, es ist immer noch in einer engen Schleife. Wie sieht Ihr Datensatz aussehen? Können Sie einfach den gesamten Datensatz in den Speicher SELECT oder mit mindestens Arbeit außerhalb von MySQL?

Wenn Sie mit, dass Daten im Speicher arbeiten, werden Sie eine deutliche Leistungssteigerung sehen.

Answer 2

So 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 erhalten.

Answer 3

ich wette, dass Maschine mehr als einen Kern hat, nicht wahr? Führen Sie es in parallel.

Python Threading

Answer 4

Hmm, nicht BFS beinhalten Markierungs Knoten, die Sie bereits gesehen haben, so dass Sie sie nicht wieder besuchen?