क्या यह चौड़ाई पहली खोज तेज हो सकती है?

Question

मेरे पास एक डेटा सेट है जो एक बड़े वजन वाले चक्रीय ग्राफ है चक्र लगभग 5-6 पथों की लूप में होते हैं। इसमें लगभग 8000 नोड होते हैं और प्रत्येक नोड में 1-6 (आमतौर पर लगभग 4-5) कनेक्शन होते हैं। मैं एकल जोड़ी सबसे छोटी पथ गणना कर रहा हूं और चौड़ाई-पहली खोज करने के लिए निम्नलिखित कोड लागू किया है।

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 

ऊपर कोड अजगर 2.6 कतार मॉड्यूल और getNeighbours() का उपयोग करता है बस एक सबरूटीन एक भी MySQL कॉल बनाता है और tuples जैसे की एक सूची के रूप में पड़ोसियों रिटर्न (('Foo',), ('बार',))। एसक्यूएल कॉल जल्दी है।

कोड काम करता है ठीक है लेकिन करने के लिए नीचे के बारे में 7 परतों की गहराई में परीक्षण चलाने के लिए के बारे में 20 सेकंड लेता है (2.5GHz इंटेल 4GB RAM ओएस एक्स 10,6)

मैं कैसे रन में सुधार करने के बारे में कोई टिप्पणी का स्वागत करते हैं चाहते हैं इस कोड का समय

Answer 1

ठीक है, टिप्पणी पर उपरोक्त दिए गए, मैं इसे अब उत्तर दूंगा।

तंग लूप में एसक्यूएल निश्चित रूप से आपको धीमा कर रहा है। मुझे परवाह नहीं है कि कॉल कितनी तेज़ है। इसके बारे में सोचें - आप एक क्वेरी को पार्स करने के लिए कह रहे हैं, एक लुकअप चलाने के लिए - जितनी जल्दी हो सके, यह अभी भी एक तंग लूप में है। आपका डेटा सेट कैसा दिखता है? क्या आप बस SELECT पूरे डेटा को मेमोरी में सेट कर सकते हैं, या कम से कम MySQL के बाहर इसके साथ काम कर सकते हैं?

यदि आप स्मृति में उस डेटा के साथ काम करते हैं, तो आपको एक महत्वपूर्ण प्रदर्शन लाभ दिखाई देगा।

Answer 2

मैं शर्त लगाऊंगा कि मशीन में एक से अधिक कोर हैं, है ना? इसे समानांतर में चलाएं।

Python Threading

Answer 3

हम्म, BFS अंकन नोड्स आप पहले से ही देखा है ताकि आप उन्हें फिर पर न जाएं नहीं शामिल करता है?

Answer 4

कुछ इस तरह:

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

आप सूचियों का एक शब्दकोश के साथ अपने एसक्यूएल प्रश्नों की जगह (और है कि मुश्किल हिस्सा होगा), तो आप इस प्रदर्शन मिल जाएगा।