Questa ricerca di ampiezza può essere effettuata più velocemente?

Question

Ho un set di dati che è un grande grafico ciclico non ponderato. I cicli si verificano in cicli di circa 5-6 percorsi. Consiste di circa 8000 nodi e ogni nodo ha da 1 a 6 (di solito circa 4-5). Sto eseguendo calcoli in una singola coppia di percorsi minimi e ho implementato il seguente codice per effettuare una ricerca in ampiezza.

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 

Il codice precedente utilizza il modulo Queue Python 2.6 e getNeighbours() è semplicemente una subroutine che effettua una singola chiamata MySQL e restituisce i vicini come una lista di tuple esempio (('Foo',), ('bar',)). La chiamata SQL è veloce.

Il codice funziona bene comunque test per fino ad una profondità di circa 7 strati richiede circa 20 secondi per eseguire (2.5GHz Intel 4GB di RAM OS X 10.6)

sarei il benvenuto qualsiasi commento su come migliorare la corsa tempo di questo codice.

Answer 1

Beh, visti i commenti positivi, farò una risposta ora.

L'SQL nel ciclo stretto è decisamente rallentando. Non mi interessa quanto sia veloce la chiamata. Pensaci: stai chiedendo di analizzare una query, di eseguire una ricerca, per quanto veloce sia, è ancora in un ciclo stretto. Come appare il tuo set di dati? Riesci solo a SELECT l'intero set di dati in memoria, o almeno a lavorare con esso al di fuori di MySQL?

Se si lavora con quei dati in memoria, si vedrà un significativo aumento delle prestazioni.

Answer 2

Scommetto che quella macchina ha più di un core, vero? Eseguilo in parallelo.

Python Threading

Answer 3

Hmm, non BFS comporta nodi di marcatura che hai già visto così non li visiti di nuovo?

Answer 4

Qualcosa di simile a questo:

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

Se si sostituiscono le query SQL con un dizionario di liste (e che sarebbe la parte difficile), si otterrà questa performance.