ツリー内のネストされた歩留まりのパフォーマンス

Question

私は木のような構造を持っています。この構造体の各要素は、ルートとなるすべての要素のEnumerableを返すことができる必要があります。このメソッドをIEnumerable<Foo> GetAll()としましょう。 {C, F, G}を返しC要素にGetAllへだから我々は

 A <-- topmost root 
    / \ 
    B  C 
/\ /\ 
    D E 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()を使用して、子-FOOSを追加しました。

私の質問は、利回りを使用しているバージョンが正しく実装されているか、改善が必要なのかどうかです（特にパフォーマンスに関して）。またはこれはちょうど悪いですか？List（またはReadOnlyCollections）に代わってください。

Answer 1

効率的にトラバースする方法を知っている1つのイテレーターではなく、大きな木のイテレーターをたくさん作成することになります。

このに関するいくつかのブログエントリ：

• ウェス・ダイアー：All about iterators
• エリックリペット：再びImmutability in C#, part 6
• エリック：Immutability in C#, part 7

それは、F＃は同等のものを持っていることは注目に値します「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; 
    } 
} 

このアプローチを

• をとるが、ネストされたイテレータ
• を大量に作成する回避必要
• より任意の複数のリストを作成回避比較的効率的です
• lの一部だけが必要な場合は、下に落ちますイスト定期

Answer 5

あなたがスタックする再帰アンロール場合にのみ1つのイテレータを持っていますので、あなたは、パフォーマンスを向上させることができます

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); 
    } 
}