Tìm kiếm theo chiều rộng đầu tiên này có thể nhanh hơn không?

Question

Tôi có một tập dữ liệu là một biểu đồ tuần hoàn không trọng số lớn Các chu kỳ xảy ra trong các vòng lặp khoảng 5-6 đường dẫn. Nó bao gồm khoảng 8000 nút và mỗi nút có từ 1-6 (thường khoảng 4-5) kết nối. Tôi đang thực hiện các phép tính đường dẫn ngắn nhất một cặp và đã triển khai mã sau để thực hiện tìm kiếm theo chiều rộng.

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 

Đoạn mã trên sử dụng các mô-đun Python 2.6 Queue và getNeighbours() chỉ đơn giản là một chương trình con mà làm cho một cuộc gọi MySQL đơn và trả về những người hàng xóm như một danh sách các hàng ví dụ (('foo',), ('bar',)). Cuộc gọi SQL nhanh chóng.

Mã công trình ok tuy nhiên thử nghiệm để xuống độ sâu khoảng 7 lớp mất khoảng 20 giây để chạy (2.5GHz Intel 4GB RAM OS X 10.6)

tôi hoan nghênh bất kỳ bình luận về làm thế nào để cải thiện thời gian thời gian của mã này.

Answer 1

Vâng, với những lời bình chọn trên nhận xét, tôi sẽ trả lời ngay bây giờ.

SQL trong vòng lặp chặt chẽ là chắc chắn làm chậm bạn xuống. Tôi không quan tâm cuộc gọi nhanh như thế nào. Hãy suy nghĩ về nó - bạn đang yêu cầu một truy vấn được phân tích cú pháp, một tra cứu được chạy - nhanh như vậy, nó vẫn còn trong một vòng lặp chặt chẽ. Bộ dữ liệu của bạn trông như thế nào? Bạn có thể chỉ cần SELECT toàn bộ dữ liệu được đặt vào bộ nhớ, hoặc ít nhất là làm việc với nó bên ngoài MySQL?

Nếu bạn làm việc với dữ liệu đó trong bộ nhớ, bạn sẽ thấy hiệu suất tăng đáng kể.

Answer 2

Tôi đặt cược rằng máy có nhiều hơn một lõi, phải không? Chạy song song.

Python Threading

Answer 3

Hmm, không BFS liên quan đến các nút đánh dấu bạn đã nhìn thấy, do đó bạn không truy cập chúng một lần nữa?

Answer 4

Something như thế này:

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

Nếu bạn thay thế các truy vấn SQL của bạn với một cuốn từ điển các danh sách (và đó sẽ là phần khó khăn), bạn sẽ có được hiệu suất này.