पेड़ में नेस्टेड उपज का प्रदर्शन

Question

मुझे पेड़ जैसी संरचना मिल गई है। इस संरचना में प्रत्येक तत्व को उन सभी तत्वों की गणना करने में सक्षम होना चाहिए जो रूट हैं। आइए इस विधि को IEnumerable<Foo> GetAll() पर कॉल करें। अगर हम C रिटर्न तत्व पर GetAll को

 A <-- topmost root 
    / \ 
    B  C 
/\ /\ 
    D E F G 

एक फोन है {C, F, G} (तत्वों के तय क्रम अच्छा होगा, लेकिन जरूरत नहीं है) तो। मुझे लगता है कि हर कोई पहले से ही जानता था।

GetAll का वर्तमान क्रियान्वयन इस तरह दिखता है:

public IEnumerable<Foo> GetAll() 
{ 
    yield return this; 

    foreach (Foo foo in MyChildren) { 
     foreach (Foo f in foo.GetAll()) { 
      yield return f; 
     } 
    } 
} 

पहले के एक कार्यान्वयन में, मैं एक सूची लौट आए और List.AddRange() का उपयोग करके जोड़ा बच्चे के कम महत्वपूर्ण चीज़ें।

मेरा सवाल यह है कि यदि उपज का उपयोग करने वाले संस्करण को लागू किया गया है या यदि इसे बेहतर किया जाना चाहिए (प्रदर्शन के संदर्भ में esp।)। या यह सिर्फ बुरा है और मुझे List एस (या ReadOnlyCollections) के बजाय चिपकना चाहिए?

Answer 1

यह प्रदर्शन के संदर्भ में निश्चित रूप से आदर्श नहीं है - आप एक ही इटरेटर के बजाय बड़े पेड़ के लिए बहुत सारे इटरेटर बनाने का प्रयास करते हैं जो जानता है कि कुशलतापूर्वक कैसे पार करना है।

कुछ ब्लॉग प्रविष्टियों इस विषय में:

• वेस डायर: All about iterators
• एरिक Lippert: Immutability in C#, part 6
• एरिक फिर से: Immutability in C#, part 7

यह ध्यान देने योग्य एफ # के बराबर है कि लायक है प्रस्तावित "yield foreach" "yield!"

Answer 2

नहीं, यह ठीक दिखता है।

मेरी blog entry पर एक नजर डालें, तो यह कुछ का उपयोग :)

Answer 3

की हो सकती है मेरी पूर्व उपज का उपयोग कर के अनुभवों के अनुसार एक सूची बनाने की तुलना में बहुत अधिक प्रभावी है। यदि आप .NET 3.5 का उपयोग कर रहे हैं, तो यह कार्यान्वयन ठीक होना चाहिए। लेकिन

yield break; 

अंत में मत भूलना। :-)

Answer 4

एक बेहतर तरीका हो सकता है कि एक विज़िट विधि बनाएं जो बार-बार पेड़ को पार करती है, और वस्तुओं को इकट्ठा करने के लिए इसका उपयोग करें।

कुछ इस तरह (एक द्विआधारी पेड़ कल्पना करते हुए):

public class Node<T> 
{ 
    public void Visit(Action<T> action) 
    { 
     action(this); 
     left.Visit(action); 
     right.Visit(action); 
    } 

    public IEnumerable<Foo> GetAll() 
    { 
     var result = new List<T>(); 
     Visit(n => result.Add(n)); 
     return result; 
    } 
} 

इस दृष्टिकोण लेते

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

Answer 5

आप प्रदर्शन में सुधार कर सकते हैं अगर आप recurse उतारना ढेर है, तो आप केवल एक इटरेटर होगा:

public IEnumerable<Foo> GetAll() 
{ 
    Stack<Foo> FooStack = new Stack<Foo>(); 
    FooStack.Push(this); 

    while (FooStack.Count > 0) 
    { 
     Foo Result = FooStack.Pop(); 
     yield return Result; 
     foreach (Foo NextFoo in Result.MyChildren) 
      FooStack.Push(NextFoo); 
    } 
}