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 が返される前にプログラムを終了するためです。反復バージョンでは、ヒープ スペースが使い果たされるまでそれが行われず、ヒープ スペースはスタック スペースの数千倍になる可能性があります。

まったく結果を出さないことは、限られた時間内に結果を出すことより明らかに悪いパフォーマンスです。

しかし、あなたの質問が本当に「ツリーが深い場合、スタックバージョンは利点を提供しますが、スタックを吹き飛ばすほど深くはありません」という場合、答えは次のとおりです。

あなたはすでに両方の方法でプログラムを書いています。実行して調べてください。 インターネット上でランダムに見知らぬ人に 2 頭の馬の写真を見せて、どちらが速いかを尋ねないでください。それらをレースし、あなたが知っているでしょう。

また、トラバーサルを実行して各要素を生成するメソッドを作成することで、問題を解決したいと思います。IEnumerable<INode> BreadthFirstTraversal(this INode node)メソッドを記述できればIEnumerable<INode> DepthFirstTraversal(this INode node)、独自の検索を記述する必要はありません。node.DepthFirstTraversal().Where(predicate).FirstOrDefault()検索したいときに言うだけです。

于 2013-03-28T14:48:58.120 に答える
4

最初にこれを明確にしましょう: 再帰は速度のためではありません。それが行うことはすべて、反復により、少なくとも同じくらい速く、多くの場合、より速く実行できます。再帰の利点は、コードが明確になることです。

そうは言っても、可能な限り最速のコードが絶対に必要な場合を除き (率直に言って、ほとんど必要ありません)、2 番目の (データ再帰的) バージョンは、理由もなく複雑になるため、検討する価値さえありません。Stack各操作にはメソッド呼び出しが含まれ、再帰を排除することは主にメソッド呼び出しを取り除くことであるため、C# では特に価値がありません。ほぼ確実に作業を追加し、ランタイムが組み込みスタックを使用してはるかに効率的に処理できるものに対してメソッド呼び出しを強制します。

エリックはスタックオーバーフローについて合理的な指摘をしていますが、それが問題になるためには、数千ノードの深さのツリーが必要になるか、すでに深いコールスタックから検索する必要があります。それ自体が再帰的であること (おそらく他の検索をトリガーすることによって)。わずかでもバランスのとれたツリーと再帰を引き起こさない述語があれば、スタックの深さは問題になりません。デフォルトのスタックは、かなりの再帰を処理するのに十分な大きさであり、必要に応じて大きくすることができます。

とはいえ、あなたと同じように、両方のバージョンを実際に実装してテストしていないすべての人もそうだと思います。そんなに気になるなら、時間を計ってください。

于 2013-03-28T14:37:09.170 に答える
0

2 番目のバージョンにはいくつかの利点があります。

スタックの代わりにキューを使用すると、DFS から BFS に簡単に切り替えることができます。

深さが大きすぎる場合、処理可能な OutOfMemoryException がスローされます。( StackOverflowException は自動的に再スローされると思います)。

再帰的なアプローチではすべてのローカル変数 (コンパイラによって生成されたものを含む) がコール スタックに保存されるため、パフォーマンスとメモリ使用量が向上する可能性があります。

于 2013-03-28T14:49:12.837 に答える