高效圖遍歷 - 消除遞歸

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

理論上，這看起來不錯，但在實踐中，我發現它比顯著用等效手寫代碼（如情況需要）更多的表現不佳通過圖表來做任何需要做的事情。我懷疑這是因爲在這種方法中，對於它返回的每一個項目，堆棧必須放鬆到某個任意深度。

我還懷疑，如果遞歸被消除，這種方法會更高效地運行。我也碰巧不擅長消除遞歸。

有誰知道如何重寫這個方法來消除遞歸？

感謝您的任何幫助。編輯： 非常感謝所有的詳細迴應。我試着對原始解決方案與Eric的解決方案進行基準比較，而不是使用枚舉器方法，而是遞歸遍歷一個lambda，奇怪的是，lambda遞歸比其他兩種方法中的任何一種都快得多。

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

其中TraverseOld是最初的方法，TraverseNew是Eric的方法，顯然lambda是lambda。

在我的機器上，TraverseOld需要10127毫秒，TraverseNew需要3038毫秒，lambda遞歸需要1181毫秒。

這是典型的枚舉器方法（與收益率返回）可以採取3X只要立即執行相反？還是有其他事情在這裏？

Answer 1

首先，你是完全正確的;如果圖中有n個節點的平均深度爲d，那麼天真的嵌套迭代器產生一個解決方案，其時間爲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 

然後遍歷是A，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); 
      } 
     } 
    } 
}