再帰のオーバーヘッド — それはどれほど深刻ですか?[重複]

StackOverflow https://stackoverflow.com/questions/4008595

質問

重複の可能性:
再帰がループよりも速いことはあるのでしょうか?

私が初めて C 言語で本格的にプログラミングする訓練を受けたのは、約 15 年前です。私の雇用主は、計算が難しいタスク向けに高度に最適化されたコードを求めていました。「再帰的なオーバーヘッド」を避けるために、読みやすさの高価であっても、ループとして再帰を書き直すように複数回アドバイスされたことを覚えています。私がそれを理解したように、再帰オーバーヘッドは、データをスタックにプッシュして後でそれを飛ばすために必要な余分な努力でした。

現在、私は C、Python、Perl、そして時々 Java でコードを書いていますが、時々再帰について疑問に思うことがあります。書き直すことでまだ得られるものはあるのでしょうか？末尾再帰の場合はどうなるでしょうか?最新のコンパイラはこれらすべての問題を無意味なものにしたのでしょうか?このような懸念はインタープリタ型言語には無関係なのでしょうか?

役に立ちましたか？

解決

再帰関数のカーネルは、関数入口/出口コードとコール自体のコストよりも少ない計算コストである場合は、

再帰はかなりのオーバーヘッドにつながることができます。見つけるための最善の方法は、コードの2つのバージョンプロファイリングするために、単純である - 。1つの再帰的、および1ないし。

再帰を回避するあなたのアイデアがスタックのような構造を自分で作ることであれば、言ったこと、気を付ける - それは必ずしも速く、より簡単な再帰的なアプローチよりではないかもしれません。ここでも、プロファイリングはあなたの友達です。

最後に、プログラマの時間がCPU時間よりも高価であることを覚えておいてください。あなたのマイクロ最適化あなたのコードの前に、実際にそれが本当に問題になるかどうかを確認するために測定することをお勧めします。

他のヒント

これは深刻です。関数呼び出し（彼らのためのコンパイラは、一般的にそう時々、それは問題ではありませんだけでなく末尾再帰を行うことができます）への真のコストを持っにおける言語Iコードのほとんど。

そのコスト、およびスタックは無制限のリソースではないという事実は、通常、私は唯一の私はそれがに行くことができる深さに制限があります知っている場合のために再帰を使用する傾向になります。

例えば、私はバランスの取れたバイナリツリーの検索が唯一の深い1兆のエントリのための50個のレベルに行くことを知っています。私はいないだろう、しかし、使用します：

def sum1through (n):
    if n == 0 return 0
    return n + sum1through (n-1)

2000万のnは、スタックのために健康ではないためにことをやって以来ます。

問題がまだ存在しています。再帰はそれには、この方法は、自分自身を呼び出すたびとして、ポインタをスタック多くのスペースを取り、そのローカル変数が再度生成されます。再帰中に行われた関数呼び出しの数はO（n）のメモリ使用を行います。ループのような非再帰関数のO（1）と比較します。

あなたが言及した言語はどれもないと思います 必要とする プラットフォーム/コンパイラーが実装するもの テールコールの除去. 。次の言語を見つけることができます。 する この最適化が必要です - ほとんどの関数型言語にはこの要件があります。

ただし、もう 1 つ考慮する必要があるのは、コンピューターは 15 年前に比べて桁違いに高速になっているため、微細な最適化について心配する必要があることは以前よりもはるかにまれになっているということです。15 年前には、適切なパフォーマンスを得るためにアセンブラで慎重に手作業で最適化する必要があったかもしれないプログラムは、たとえ Java のような高水準言語で書かれていたとしても、最新のコンピュータでは非常に高速に実行される可能性があります。パフォーマンスがまったく問題にならないというわけではありませんが、パフォーマンスを選択することに集中する必要があります。 正しいアルゴリズム そして書く上で 読める コード。マイクロ最適化は、パフォーマンスを測定し、問題のコードがボトルネックであることがわかった後にのみ行ってください。

一つあなたは する ただし、スタックがオーバーフローすることを心配する必要があります。そのようなことが起こるリスクがある場合は、代わりに反復的な方法で再帰関数を書き直す価値があるかもしれません。

人々はパフォーマンスについて愚かなことをたくさん言います。

  1. もし、あんたが 必要 再帰、深さ優先のツリーウォークを行う場合は、それが必要なので、それを使用します。

  2. 性能を心配する前に、 何でも, 、問題があるかどうか、そしてそれがどこにあるのかを調べます。
    パフォーマンスの問題は詐欺師やトリックスターのようなものです。パフォーマンスの問題は、予想外の場所に特化しているため、再帰などの特定のことを心配している場合は、ほぼ間違いなく間違ったことを心配していることになります。

私の意見では、パフォーマンスの問題を見つける最善の方法はスタック サンプリングです。 壁時計の時間で, 、 そして サンプルを調べてプログラムが何をしているかを確認する, 単に測定値を取得して、その意味を疑問に思うだけではありません。

とはいえ、再帰呼び出しに 10% 以上の時間がかかっていて、再帰ルーチン内で他に大したことが起こらず、それをループできる場合は、ループするとおそらく役に立ちます。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top