[解決済み] yield (return)を使ってはいけない場合 [重複]について

質問

この質問はすでにここに回答があります。

IEnumerableを返すときに'yield return'を使わない理由はありますか？

このSOには、以下の利点に関する有益な質問がいくつかあります。 yield return . 例えば

• 誰かyieldについて教えてください。 キーワード

• c# yieldの面白い使い方
  
  キーワード

• イールドキーワードとは

についての意見を募集しています。 NOT を使用します。 yield return . 例えば、コレクション内のすべての項目を返す必要があると予想される場合、それは 見える のように yield が便利ですよね？

を使用するケースはどのようなものがありますか？ yield 制限される、不必要、トラブルに巻き込まれる、あるいは避けるべきですか？

解決方法は？

yieldの使用が制限される場合、不必要な場合、トラブルに巻き込まれる場合、その他避けるべき場合とはどのようなものでしょうか？

再帰的に定義された構造を扱う場合、"yield return"の使用について慎重に考えることをお勧めします。例えば、こんなのをよく見かけます。

public static IEnumerable<T> PreorderTraversal<T>(Tree<T> root)
{
    if (root == null) yield break;
    yield return root.Value;
    foreach(T item in PreorderTraversal(root.Left))
        yield return item;
    foreach(T item in PreorderTraversal(root.Right))
        yield return item;
}

見た目は申し分ないのですが、性能に問題があります。ツリーの深さがhであるとする。そうすると、最大でO(h)個のネストしたイテレータが構築されることになる。外側のイテレータで "MoveNext" を呼び出すと、O(h) 個のネストした MoveNext の呼び出しが発生します。これはn個のアイテムを持つ木に対してO(n)回実行されるので、このアルゴリズムはO(hn)になります。 そして、二分木の高さは lg n <= h <= n なので、このアルゴリズムは時間ではよくて O(n lg n)、悪くても O(n^2) で、スタックスペースではよい場合で O(lg n)、悪い場合で O(n) となることを意味しているのです。各列挙体はヒープに割り当てられるので、ヒープ空間では O(h) となります。 (私が知っているC#の実装では、適合する実装は他のスタックやヒープ空間の特性を持つかもしれません)。

しかし、木の反復は時間がO(n)、スタックスペースがO(1)になることがあります。 代わりにこんな風に書けばいい。

public static IEnumerable<T> PreorderTraversal<T>(Tree<T> root)
{
    var stack = new Stack<Tree<T>>();
    stack.Push(root);
    while (stack.Count != 0)
    {
        var current = stack.Pop();
        if (current == null) continue;
        yield return current.Value;
        stack.Push(current.Left);
        stack.Push(current.Right);
    }
}

はまだ yield return を使っていますが、よりスマートになっています。これで、時間はO(n)、ヒープスペースはO(h)、スタックスペースはO(1)となりました。

さらに詳しく：Wes Dyerの記事を参照してください。

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