使用LINQ进行高效的图遍历 – 消除递归
今天，我将实现一种方法来遍历任意深度的图形并将其展平为单个可枚举的图形。 相反，我先做了一点搜索，发现了这个：
public static IEnumerable Traverse(this IEnumerable enumerable, Func<T, IEnumerable> recursivePropertySelector) { foreach (T item in enumerable) { yield return item; IEnumerable seqRecurse = recursivePropertySelector(item); if (seqRecurse == null) continue; foreach (T itemRecurse in Traverse(seqRecurse, recursivePropertySelector)) { yield return itemRecurse; } } } 从理论上讲，这看起来不错，但实际上我发现它比使用等效的手写代码（如果出现的情况）执行图表并做任何需要做的事情要差得多。 我怀疑这是因为在这种方法中，对于它返回的每个项目，堆栈必须放松到某个任意深度的水平。
我还怀疑如果递归被消除，这种方法会更有效地运行。 我也碰巧不太擅长消除递归。
有谁知道如何重写这种方法来消除递归？
谢谢你的帮助。
编辑：非常感谢所有详细的回复。 我已尝试对原始解决方案与Eric的解决方案进行基准测试，而不是使用枚举器方法，而是递归遍历一个lambda，奇怪的是，lambda递归明显快于其他两种方法。
class Node { public List ChildNodes { get; set; } public Node() { ChildNodes = new List(); } } class Foo { public static void Main(String[] args) { var nodes = new List(); 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 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 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 ms，TraverseNew需要3038 ms，lambda递归需要1181 ms。
这种典型的枚举器方法（带有yield return）可能需要3倍才能立即执行吗？ 或者是其他事情发生在这里？
首先，你是绝对正确的; 如果图形具有n个平均深度为d的节点，则原始嵌套迭代器产生的解决方案是时间为O（n * d），堆栈中为O（d）。 如果d是n的一小部分，那么这可以成为O（n 2 ）算法，如果d很大，那么你可以完全吹掉堆栈。
如果您对嵌套迭代器的性能分析感兴趣，请参阅前C＃编译器开发人员Wes Dyer的博客文章：
http://blogs.msdn.com/b/wesdyer/archive/2007/03/23/all-about-iterators.aspx
dasblinkenlight的解决方案是标准方法的变体。 我通常会写这样的程序：
public static IEnumerable Traverse ( T root, Func> children) { var stack = new Stack (); 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 Traverse ( IEnumerable roots, Func> 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 Closure ( T root, Func> children) { var seen = new HashSet (); var stack = new Stack (); 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/
特别是：
你是对的，在代码中递归地运行树和图形，确实yield return是效率低下的一个重要原因。
通常，您使用堆栈重写递归代码 – 与通常在编译代码中实现的方式类似。
我没有机会尝试一下，但这应该有效：
public static IEnumerable Traverse (this IEnumerable enumerable, Func> recursivePropertySelector) { var stack = new Stack>(); 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); } } } }
您总是可以通过复制递归与堆栈一起工作的基础来消除递归。
- 将第一个项目放在堆栈顶部
- 当堆栈不为空时，从堆栈中弹出一个项目
- 如果当前节点有子节点，则将它们添加到堆栈中
- 收益率返回当前项目。
- 转到第1步！
疯狂聪明的理论答案： https ： //stackoverflow.com/a/933979/29093
http://cs.saddleback.edu/rwatkins/CS2B/Lab%20Exercises/Stacks%20and%20Recursion%20Lab.pdf
您可以在代码中使用队列。 队列可以初始化为列表，其中一个元素等于顶层节点。 然后，您必须从第一个元素开始遍历列表中的每个元素。 如果第一个元素包含子节点，则将它们全部附加到队列的末尾。 然后移动到下一个元素。 当您到达队列末尾时，您的图表将完全展平。