3

私は、時には20〜30レベルの深さの大きなオブジェクトグラフを歩く必要があるコンポーネントを書いています。

グラフを歩く最もパフォーマンスの高い方法は何ですか？

A.深い再帰を回避するために「ステップ」をキューに入れる

また

B. DFS（深さ優先探索）。多くのレベルを深くステップし、「深い」スタックトレースを持つ場合があります。

私が尋ねている質問は、「深い」スタックトレースを引き起こすDFSを実行することで.NETにパフォーマンスの低下がありますか？もしそうなら、ヒットは何ですか？また、DFSで再帰的に処理されるステップをキューに入れることで、BFSを使用したほうがよいでしょうか。

不明な点がある場合は申し訳ありません。ありがとう。

4

3 に答える 3

4

実行時に、深いスタックでのコード実行が浅い呼び出しスタックよりも遅くなる原因となるものはありません。通常、コードの実行はスタックウォークをトリガーしないため、その理由はありません。

私が通常言うとき、これはいくつかの例外があることを意味します：

  • セキュリティ/証拠チェックは通常、現在のセキュリティコンテキストを判断するためにコールスタックをウォークします
  • もちろん、例外をスローしてキャッチします（とにかく、それを中止することを除いて、ツリートラバーサルでそれを行いたくありません）

反復または再帰的なツリートラバーサルを実装する必要があるかどうかは、.NETランタイムが一方のシナリオで他方のシナリオよりも優れたパフォーマンスを提供するかどうかに依存しませんが、Big-O（時間とメモリ）に基づいて決定する必要があります。特に大きな木のための場合。私たちがいる場所を考えると、再帰的なソリューションでスタックオーバーフローが発生する可能性を思い出させる必要はないと思います...ただし、末尾呼び出しの最適化は可能です。

ツリーとトラバーサルの目的でBig-Oの最速のトラバーサルを選択したら、実装の最適化について心配することができます。

于 2011-01-16T01:03:42.800 に答える
1

.NET / C＃が末尾呼び出しの再帰を最適化しないのはなぜですか？を参照してください。。どうやら、.NETはx86-64で末尾再帰の最適化を実行するため、それがアーキテクチャであり、コードがそのような最適化に適している場合は、再帰を使用してください。

于 2011-01-16T01:04:13.453 に答える
1

あなたはある程度分離されるべきである2つの概念を混ぜ合わせています：

  • データ構造の反復と、呼び出しスタックが構造になる再帰関数の使用。

  • 幅優先対深さ優先トラバーサル。

再帰関数が深さ優先を実装する傾向がある限り、これらは接続されています。ただし、キューを使用する場合、幅優先に制限するものは何もありません。

幅優先が必要な場合はFIFOキューを使用し、深さ優先が必要な場合はLIFOキューを使用します。どちらの方法でも、関数呼び出しのオーバーヘッド（おそらくかなりマイナーであり、キューのメソッドの呼び出しは、オプティマイザーによってインライン化されない場合はコストがかかる可能性があります）とシステムコールスタックのスタックスペース使用量を節約できます。

于 2011-01-16T01:09:53.177 に答える