深度优先搜索的递归方法与堆栈 [英] Recursive Approach versus Stack for Depth First Search

问题描述

我有如下方法，该方法搜索集合并递归评估条件:

I have a method as below which searches a collection and evaluates a condition recursively:

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

或者，可以使用堆栈来实现此目的，以避免如下所示的递归:

Alternatively this can be implemented using a stack to avoid recursion as below:

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

我的问题是，与递归版本相比，当树的深度较大时，堆栈版本是否对性能有好处?

My question is, does the stack version offer any performance benefits when the depth of the tree is large compared to the recursive version?

推荐答案

我的问题是，与递归版本相比，当树的深度较大时，堆栈版本是否对性能有好处?

My question is, does the stack version offer any performance benefits when the depth of the tree is large compared to the recursive version?

是的.当树的深度很大时，递归版本比迭代版本无限慢.这是因为递归版本将破坏调用堆栈，导致不可阻挡的堆栈外空间异常，并在返回布尔值之前终止程序.迭代版本在堆空间用尽之前不会这样做，并且堆空间可能比堆栈空间大数千倍.

Yes. The recursive version is infinitely slower than the iterative version when the depth of the tree is large. That's because the recursive version will blow the call stack, cause an unstoppable out-of-stack-space exception, and terminate your program before the bool is returned. The iterative version will not do that until heap space is exhausted, and heap space is potentially thousands of times larger than stack space.

根本不给出结果显然比在任何有限的时间内给出结果都要糟糕.

Not giving a result at all is obviously worse performance than giving a result in any finite amount of time.

但是，如果您的问题确实是当树很深时堆栈版本是否有任何好处，但不会深到会炸毁堆栈"，那么答案是:

If however your question really is "does the stack version offer any benefit when the tree is deep, but not so deep that it blows the stack" then the answer is:

您已经用两种方法编写了程序.运行它并找出答案.不要在网上看到两匹马的随机陌生人，而是问哪个更快.比赛他们，然后您就会知道.

You've already written the program both ways. Run it and find out. Don't show random strangers on the internet pictures of two horses and ask which is faster; race them and then you'll know.

也:我倾向于通过编写遍历并屈服每个元素的方法来解决您的问题.如果可以编写方法，则 IEnumerable< INode>BreadthFirstTraversal(此INode节点)和 IEnumerable< INode>DepthFirstTraversal(此INode节点)，那么您无需编写自己的搜索；您只需在要搜索时说 node.DepthFirstTraversal().Where(predicate).FirstOrDefault().

Also: I would be inclined to solve your problem by writing methods that do traversals and yield each element. If you can write methods IEnumerable<INode> BreadthFirstTraversal(this INode node) and IEnumerable<INode> DepthFirstTraversal(this INode node) then you don't need to be writing your own search; you can just say node.DepthFirstTraversal().Where(predicate).FirstOrDefault() when you want to search.

这篇关于深度优先搜索的递归方法与堆栈的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！