11

重複の可能性：
再帰はループよりも高速ですか？

私は約15年前に、Cで真剣にプログラムするように最初に訓練されました。私の雇用主は、計算が難しいタスクのために高度に最適化されたコードを望んでいました。「再帰のオーバーヘッド」を回避するために、読みやすさを犠牲にしても、再帰をループとして書き直すように何度もアドバイスされたことを覚えています。そのとき私が理解したように、再帰オーバーヘッドは、データをスタックにプッシュし、後でそれをポップオフするために必要な余分な労力でした。

今、私はC、Python、Perl、そして時にはJavaでコーディングしていますが、再帰について時々疑問に思います。それらを書き直すことで得られるものはまだありますか？それらが末尾再帰である場合はどうなりますか？最近のコンパイラはこれらすべての問題を解決しましたか？そのような懸念は通訳言語には無関係ですか？

4

5 に答える 5

19

再帰関数のカーネルが関数の開始/終了コードおよび呼び出し自体のコストよりも計算コストが低い場合、再帰は大きなオーバーヘッドにつながる可能性があります。見つけるための最良の方法は、コードの2つのバージョンをプロファイルすることです。1つは再帰的で、もう1つはそうではありません。

とはいえ、再帰を回避するという考えがスタックのような構造を自分で作成することである場合は、注意してください。これは、より単純な再帰的アプローチよりも必ずしも高速であるとは限りません。繰り返しますが、プロファイリングはあなたの友達です。

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

于 2010-10-24T14:20:17.840 に答える
3

問題はまだ存在します。メソッドがそれ自体を呼び出すたびに、そのメソッドへのポインターとそのローカル変数が再度生成されるため、再帰には多くのスタックスペースが必要です。再帰中に行われた関数呼び出しの数により、O（n）のメモリ使用量が発生します。ループのような非再帰関数のO（1）と比較して。

于 2010-10-24T14:17:49.707 に答える
2

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

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

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

于 2010-10-24T14:16:42.450 に答える
2

大変です。私がコーディングする言語のほとんどは、関数呼び出しに実際のコストがかかります（それらのコンパイラーは通常、末尾再帰も実行できるため、問題にならない場合もあります）。

そのコストと、スタックが無制限のリソースではないという事実により、通常、再帰を使用する傾向があるのは、到達できる深さに制限があることがわかっている場合のみです。

たとえば、バランスの取れた二分木検索は、1兆のエントリに対して50レベルの深さしか実行されないことを私は知っています。ただし、以下は使用しません。

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

なぜなら、n2000万のそれを行うことはスタックにとって健康的ではないからです。

于 2010-10-24T14:16:55.263 に答える
1

人々はパフォーマンスについて多くのばかげたことを言います。

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

  2. 何かのパフォーマンスを心配する前に、問題があるかどうか、そしてそれがどこにあるかを調べてください。
    パフォーマンスの問題は詐欺師やトリックスターのようなものです。彼らはあなたが最も期待しない場所にいることに特化しているので、再帰のような特定のことを心配している場合は、間違ったことを心配することはほぼ確実です。

私の意見では、パフォーマンスの問題を見つける最良の方法は、実時間でスタックサンプリングを行い、サンプルを調べて、測定値を取得してその意味を理解するだけでなく、プログラムが何を行っているかを確認することです。

とは言うものの、再帰呼び出しに10％以上の時間がかかり、再帰ルーチン内で他に何も起こらず、ループできる場合は、ループすることがおそらく役立つでしょう。

于 2010-10-24T16:45:57.623 に答える