yield (return) を使用しない場合 [重複] 質問する

Question

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」を呼び出すと、MoveNext への O(h) 個のネストされた呼び出しが行われます。これは 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

Answer 1

yield の使用が制限的、不必要、トラブルの原因、または回避する必要があるケースとはどのような場合ですか?