7

我有一个方法如下，它搜索一个集合并递归地评估一个条件：

public static bool Recurse(this INodeViewModel node, Func<INodeViewModel,bool> predicate)
{
   INodeViewModel currentNode = node;

   return predicate(currentNode) || node.Children.Select(x => Recurse(x, predicate)).Any(found => found);
}

或者，这可以使用堆栈来实现以避免递归，如下所示：

public static bool UsingStack(this INodeViewModel node, Func<INodeViewModel, bool> predicate)
{
   var stack = new Stack<INodeViewModel>();
   stack.Push(node);

   while(stack.Any())
   {
       var current = stack.Pop();

       if (predicate(current))
           return true;

       foreach (var child in current.Children)
       {
           stack.Push(child);
       }
   }
   return false;
}

我的问题是，与递归版本相比，当树的深度很大时，堆栈版本是否提供任何性能优势？

4

3 回答 3

22

我的问题是，与递归版本相比，当树的深度很大时，堆栈版本是否提供任何性能优势？

是的。当树的深度很大时，递归版本比迭代版本慢得多。这是因为递归版本会破坏调用堆栈，导致不可停止的堆栈空间外异常，并在返回 bool 之前终止程序。迭代版本在堆空间耗尽之前不会这样做，并且堆空间可能比堆栈空间大数千倍。

根本不给出结果显然比在任何有限时间内给出结果更差。

但是，如果您的问题确实是“当树很深时堆栈版本是否提供任何好处，但又不会太深以至于炸毁堆栈”，那么答案是：

您已经以两种方式编写了程序。运行它并找出答案。 不要在网上随便给陌生人看两匹马的照片，问哪个更快；比赛他们，然后你就会知道。

另外：我倾向于通过编写遍历并产生每个元素的方法来解决您的问题。如果您可以编写方法IEnumerable<INode> BreadthFirstTraversal(this INode node)，IEnumerable<INode> DepthFirstTraversal(this INode node)那么您就不需要编写自己的搜索；你可以说什么node.DepthFirstTraversal().Where(predicate).FirstOrDefault()时候要搜索。

于 2013-03-28T14:48:58.120 回答
4

让我们先明确一点：递归不是为了速度。它所做的任何事情都可以通过迭代至少以同样快的速度完成，而且通常更快。递归的好处在于代码的清晰性。

话虽如此，除非您绝对需要尽可能快的代码（坦率地说，您几乎从不这样做），否则第二个（数据递归）版本甚至不值得考虑，因为它无缘无故地增加了复杂性。它在 C# 中尤其没有价值，因为每个Stack操作都涉及一个方法调用，而消除递归主要是为了摆脱方法调用。您几乎肯定会添加工作，强制方法调用运行时可以使用内置堆栈更有效地处理的内容。

Eric 对堆栈溢出提出了一个合理的观点，但为了解决这个问题，您需要一棵树深数千个节点，或者您必须从已经很深的调用堆栈中搜索，或者谓词需要本身是递归的（可能通过触发其他搜索）。有了一个稍微平衡的树和一个不会导致更多递归的谓词，堆栈深度应该不是问题；默认堆栈已经足够大，可以处理相当多的递归，如果需要，可以做得更大。

尽管如此：我猜想，你也一样，所有没有实际实现和测试过这两个版本的人也是如此。如果你那么在乎，那就抓紧时间吧。

于 2013-03-28T14:37:09.170 回答
0

第二个版本有几个优点：

您可以使用队列而不是堆栈轻松地从 DFS 切换到 BFS。

如果深度太大，它会抛出一个可以处理的 OutOfMemoryException。（我相信 StackOverflowException 会自动重新抛出）。

性能和内存使用可能会更好，因为递归方法将所有局部变量（包括编译器生成的）保存在调用堆栈上。

于 2013-03-28T14:49:12.837 回答