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

グラフを通って実行する必要があるものはすべて実行します。これは、このメソッドでは、返されるすべてのアイテムについて、スタックが任意の深いレベルに巻き戻されなければならないためです。

また、この方法は、再帰が排除された場合、より効率的に実行されると考えられます。私はまた、再帰を排除することにはあまりうまくいきません。

再帰を排除するためにこのメソッドを書き換える方法を知っている人はいますか？

ありがとうございました。

EDIT： すべての詳細な対応についてありがとうございます。私は元の解とベンチマークを比較しようとしましたが、エリックの解法と列挙法を使用せず、代わりにラムダで巡回し、奇妙なことに、ラムダ再帰は他の2つの方法よりも大幅に高速です。

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

ここで、TraverseNldは元の方法ですが、TraverseNewはEricの方法であり、明らかにラムダはラムダです。

私のマシンでは、TraverseOldは10127 ms、TraverseNewは3038 ms、ラムダ再帰は1181 msです。

これは典型的なもので、列挙型メソッド（yield returns with）は即時実行に比べて3倍長くかかる可能性がありますか？それとも何か別のことが起こっていますか？

Answer 1

まず第一に、あなたは絶対に正しいです。グラフが平均深度dのn個のノードを有する場合、ナイーブネストされたイテレータは、時間的にO（n * d）、スタックにO（d）である解をもたらす。 dがnの大きな部分である場合、これはO（n ）アルゴリズムになり、dが大きい場合はスタック全体を吹き飛ばすことができます。

あなたは、ネストされたイテレータのパフォーマンス分析に興味がある場合は、元のC＃コンパイラの開発者ウェス・ダイアーのブログ記事を参照してください。

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 

次いでトラバーサルは、B、D、C、D、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); 
      } 
     } 
    } 
}