LINQ के साथ कुशल ग्राफ ट्रैवर्सल - रिकर्सन को हटाएं

Question

आज मैं एक मनमाने ढंग से गहरे ग्राफ को पार करने के लिए एक विधि को लागू करने जा रहा था और इसे एक समरूप में फ़्लैट कर रहा था। इसके बजाय, मैं एक छोटे से खोज पहले किया था और यह पाया:

public static IEnumerable<T> Traverse<T>(this IEnumerable<T> enumerable, Func<T, IEnumerable<T>> recursivePropertySelector) 
{ 
    foreach (T item in enumerable) 
    { 
     yield return item; 

     IEnumerable<T> seqRecurse = recursivePropertySelector(item); 

     if (seqRecurse == null) continue; 
     foreach (T itemRecurse in Traverse(seqRecurse, recursivePropertySelector)) 
     { 
      yield return itemRecurse; 
     } 
    } 
} 

सिद्धांत रूप में यह अच्छा लग रहा है, लेकिन व्यवहार में मैंने पाया यह काफी बराबर हाथ से लिखा कोड का उपयोग कर (स्थिति उत्पन्न होती है के रूप में) की तुलना में अधिक खराब प्रदर्शन एक ग्राफ के माध्यम से जाने के लिए और जो कुछ भी करने की जरूरत है करने के लिए। मुझे संदेह है कि ऐसा इसलिए है क्योंकि इस विधि में, प्रत्येक आइटम के लिए यह लौटाता है, स्टैक को कुछ मनमाने ढंग से गहरे स्तर से खोलना पड़ता है।

मुझे यह भी संदेह है कि अगर रिकर्सन समाप्त हो गया है तो यह विधि बहुत अधिक कुशलता से चलती है। मैं भी रिकर्सन को खत्म करने में बहुत अच्छा नहीं होता।

क्या किसी को पता है कि रिकर्सन को खत्म करने के लिए इस विधि को फिर से लिखना है?

किसी भी मदद के लिए धन्यवाद।

संपादित करें: सभी विस्तृत प्रतिक्रियाओं के लिए बहुत बहुत धन्यवाद। मैंने एरिक के समाधान बनाम मूल समाधान बेंचमार्किंग की कोशिश की है, जो एक गणक विधि का उपयोग नहीं कर रहा है और बदले में एक लैम्ब्डा के साथ उलझन में चल रहा है और विचित्र रूप से, लैम्ब्डा रिकर्सन दो अन्य विधियों में से किसी एक की तुलना में काफी तेज़ है।

class Node 
{ 
    public List<Node> ChildNodes { get; set; } 

    public Node() 
    { 
     ChildNodes = new List<Node>(); 
    } 
} 

class Foo 
{ 
    public static void Main(String[] args) 
    { 
     var nodes = new List<Node>(); 
     for(int i = 0; i < 100; i++) 
     { 
      var nodeA = new Node(); 
      nodes.Add(nodeA); 
      for (int j = 0; j < 100; j++) 
      { 
       var nodeB = new Node(); 
       nodeA.ChildNodes.Add(nodeB); 
       for (int k = 0; k < 100; k++) 
       { 
        var nodeC = new Node(); 
        nodeB.ChildNodes.Add(nodeC); 
        for(int l = 0; l < 12; l++) 
        { 
         var nodeD = new Node(); 
         nodeC.ChildNodes.Add(nodeD); 
        } 
       } 
      } 
     }    

     nodes.TraverseOld(node => node.ChildNodes).ToList(); 
     nodes.TraverseNew(node => node.ChildNodes).ToList(); 

     var watch = Stopwatch.StartNew(); 
     nodes.TraverseOld(node => node.ChildNodes).ToList(); 
     watch.Stop(); 
     var recursiveTraversalTime = watch.ElapsedMilliseconds; 
     watch.Restart(); 
     nodes.TraverseNew(node => node.ChildNodes).ToList(); 
     watch.Stop(); 
     var noRecursionTraversalTime = watch.ElapsedMilliseconds; 

     Action<Node> visitNode = null; 
     visitNode = node => 
     { 
      foreach (var child in node.ChildNodes) 
       visitNode(child); 
     }; 

     watch.Restart(); 
     foreach(var node in nodes) 
      visitNode(node); 
     watch.Stop(); 
     var lambdaRecursionTime = watch.ElapsedMilliseconds; 
    } 
} 

कहाँ TraverseOld मूल विधि है, TraverseNew एरिक के तरीका है, और जाहिर है लैम्ब्डा लैम्ब्डा है।

मेरी मशीन पर, ट्रैवर्सऑल्ड 10127 एमएस लेता है, ट्रैवर्सन्यू 3038 एमएस लेता है, लैम्ब्डा रिकर्सन 1181 एमएस लेता है।

क्या यह सामान्य है कि गणनाकर्ता विधियां (उपज रिटर्न के साथ) तत्काल निष्पादन के विरोध में 3 एक्स तक ले सकती हैं? या यहाँ कुछ और चल रहा है?

Answer 1

सबसे पहले, आप बिल्कुल सही कर रहे हैं; यदि ग्राफ़ में औसत गहराई डी के एन नोड्स हैं तो बेवकूफ नेस्टेड इटरेटर्स एक समाधान उत्पन्न करते हैं जो समय में ओ (एन * डी) होता है, और ओ (डी) स्टैक में होता है। यदि डी n का बड़ा अंश है तो यह ओ (एन) एल्गोरिदम बन सकता है, और यदि डी बड़ा है तो आप पूरी तरह से ढेर को उड़ सकते हैं।

आप नेस्टेड iterators का एक प्रदर्शन विश्लेषण में रुचि रखते हैं, पूर्व सी # संकलक डेवलपर वेस डायर के ब्लॉग पोस्ट देखें:

http://blogs.msdn.com/b/wesdyer/archive/2007/03/23/all-about-iterators.aspx

dasblinkenlight के समाधान मानक दृष्टिकोण पर एक भिन्नता है। मैं आम तौर पर इस तरह प्रोग्राम लिखने होगा:

public static IEnumerable<T> Traverse<T>(
    T root, 
    Func<T, IEnumerable<T>> children) 
{ 
    var stack = new Stack<T>(); 
    stack.Push(root); 
    while(stack.Count != 0) 
    { 
     T item = stack.Pop(); 
     yield return item; 
     foreach(var child in children(item)) 
      stack.Push(child); 
    } 
} 

और फिर यदि आप कई जड़ें:

public static IEnumerable<T> Traverse<T>(
    IEnumerable<T> roots, 
    Func<T, IEnumerable<T>> children) 
{ 
    return from root in roots 
      from item in Traverse(root, children) 
      select item ; 
} 

अब

, ध्यान दें कि एक ट्रेवर्सल नहीं है कि आप क्या चाहते हैं यदि आप एक अत्यधिक परस्पर है ग्राफ या एक चक्रीय ग्राफ! आप नीचे की ओर इशारा करते तीर के साथ एक ग्राफ है:

  A 
     /\ 
     B-->C 
     \/
      D 

तो ट्रेवर्सल ए, बी, डी, सी, डी, सी, डी है आप एक चक्रीय या परस्पर ग्राफ है तो आप क्या चाहते हैं है पारगमन बंद।

public static IEnumerable<T> Closure<T>(
    T root, 
    Func<T, IEnumerable<T>> children) 
{ 
    var seen = new HashSet<T>(); 
    var stack = new Stack<T>(); 
    stack.Push(root); 

    while(stack.Count != 0) 
    { 
     T item = stack.Pop(); 
     if (seen.Contains(item)) 
      continue; 
     seen.Add(item); 
     yield return item; 
     foreach(var child in children(item)) 
      stack.Push(child); 
    } 
} 

यह भिन्नता केवल उन वस्तुओं को उत्पन्न करती है जो पहले नहीं मिली हैं।

मैं भी रिकर्सन को खत्म करने में बहुत अच्छा नहीं होता।

मैंने रिकर्सन को खत्म करने के तरीके और सामान्य रूप से पुनरावर्ती प्रोग्रामिंग के बारे में कई लेख लिखे हैं। इस विषय अपनी रुचि, तो देखें:

http://blogs.msdn.com/b/ericlippert/archive/tags/recursion/

विशेष रूप से:

http://blogs.msdn.com/b/ericlippert/archive/2005/08/01/recursion-part-two-unrolling-a-recursive-function-with-an-explicit-stack.aspx

http://blogs.msdn.com/b/ericlippert/archive/2005/08/04/recursion-part-three-building-a-dispatch-engine.aspx

http://blogs.msdn.com/b/ericlippert/archive/2005/08/08/recursion-part-four-continuation-passing-style.aspx

Answer 2

आप अपने कोड में एक कतार का उपयोग कर सकते हैं। कतार को एक सूची के रूप में प्रारंभ किया जा सकता है जिसमें शीर्ष नोड के बराबर एक तत्व होता है। फिर आपको पहले से शुरू होने वाली सूची के प्रत्येक तत्व के माध्यम से फिर से शुरू करना होगा। यदि पहले तत्व में बच्चे नोड्स होते हैं, तो आप उन्हें कतार के अंत में जोड़ देते हैं। फिर अगले तत्व पर जाएं। जब आप कतार के अंत तक पहुंचते हैं तो आपका ग्राफ पूरी तरह से फ़्लैट हो जाएगा।

Answer 3

आप स्टैक के साथ कैसे काम करते हैं, इसकी मूल बातें दोहराकर आप हमेशा रिकर्सन को खत्म कर सकते हैं।

1. जगह ढेर
2. के शीर्ष पर पहले आइटम जबकि ढेर खाली नहीं है,,
3. ढेर बंद एक आइटम पॉप अगर वर्तमान नोड बच्चे हैं उन्हें ढेर में जोड़ने
4. यील्ड वर्तमान आइटम लौटाता है।
5. चरण 1 पर जाएं!

पागल स्मार्ट सैद्धांतिक जवाब: https://stackoverflow.com/a/933979/29093

http://cs.saddleback.edu/rwatkins/CS2B/Lab%20Exercises/Stacks%20and%20Recursion%20Lab.pdf

Answer 4

आप ठीक कह रहे हैं, रिकर्सिवली कोड कि yield return करता है में पेड़ों और रेखांकन चलने अक्षमता का एक बड़ा स्रोत है।

आम तौर पर, आप एक स्टैक के साथ रिकर्सिव कोड को फिर से लिखते हैं - इसी तरह से इसे आमतौर पर संकलित कोड में कैसे कार्यान्वित किया जाता है।

मैं इसे आज़माने के लिए एक मौका नहीं मिला है, लेकिन इस काम करना चाहिए:

public static IEnumerable<T> Traverse<T>(this IEnumerable<T> enumerable, Func<T, IEnumerable<T>> recursivePropertySelector) { 
    var stack = new Stack<IEnumerable<T>>(); 
    stack.Push(enumerable); 
    while (stack.Count != 0) { 
     enumerable = stack.Pop(); 
     foreach (T item in enumerable) { 
      yield return item; 
      var seqRecurse = recursivePropertySelector(item); 
      if (seqRecurse != null) { 
       stack.Push(seqRecurse); 
      } 
     } 
    } 
}