7

数値 n の階乗を計算する 2 つの関数があります。「通常の」関数が数値 n の階乗を計算するのに必要な時間が短い理由がわかりません。これは通常の機能です:

double factorial(int n) {
    double s = 1;
    while (n > 1) {
        s *= n;
        --n;        
    }

    return s;
}

そして、これは再帰関数です:

double factorial(int n) {
    if (n < 2) return 1;
    return n * factorial(n-1);
}

新しい変数を作成しないため、時間がかからず、操作も少なくなります。通常の関数が少し多くのメモリを使用するのは事実ですが、より高速です。

どちらを使用する必要があり、その理由は?

PS: e^x のテイラー級数を計算するために必要だったので、double を使用しています。

4

5 に答える 5

6

あなたは、再帰関数は「新しい変数を作成せず、操作も少ないため、時間がかからないはずだ」と書いています。最初の主張はかなり無意味です。ローカル変数のメモリは、通常、関数に入ったときに 1 回の減算操作によって割り当てられます。これには、わずかな時間がかかります (人間が知る最速の割り当てです)。2 番目のアサーションは、C++ 実装に対して単純に false です。コンパイラで再帰関数が遅いことを測定したので、それはそれ以下ではなく、より多くのことを行います。

さて、なぜ。

各呼び出しは、戻りアドレスと実際の引数をスタックにコピーする必要があります。これには時間がかかります。さらに、デバッグと例外をサポートするために、通常、各関数呼び出しは、呼び出し前のスタックの状態に関する情報を本質的に格納する、niceスタック フレームを確立する追加の作業を行います。

ただし、再帰的なバリアントは遅くする必要はありません。しかし、ほとんど逆説的ですが、実際には反復バージョンと同じくらい高速なバリアントは、より多くのことを行うように見えます... アイデアは、コンパイラがそれを反復バージョンに変換できるように、つまり、コンパイラができるように書くことです。再帰呼び出し (時間がかかる) を単純なループに置き換えます。

唯一の問題は、私の知る限り、この種の最適化を行う C++ コンパイラはほとんどないということです。:-(

ただし、完全を期すために、再帰呼び出しが 1 つだけであること、およびそれが最後に発生することを確認することが考えられます。これは末尾再帰と呼ばれます。現在の再帰コード、

double factorial( int n )
{
    if( n < 2 ) { return 1; }
    return n*factorial( n-1 );
}

再帰呼び出しの後に による乗算があるため、末尾再帰ではありませんn。

末尾再帰にするために、最後に実行する必要があることを実行するために必要な情報を引数として渡すことができます*n。そのために必要な情報は、 の値とn、それを実行する必要があるという事実です。これは、適切な仮引数を持つヘルパー関数を導入することを意味します。

double factorialScaledBy( double m, int n )
{
    if( n < 2 ) { return m*1; }

    // Same as "n*factorialScaledBy( m, n-1 )", but tail-recursive:
    return factorialScaledBy( n*m, n-1 );  
}

double factorial( int n )
{
    return factorialScaledBy( 1, n );
}

これで、十分にスマートなコンパイラは、再帰呼び出し後の関数実行で何も起こらないことに気付くことができます。したがって、ローカル変数は使用されず、再帰呼び出しに再利用できます。したがって、シミュレートされた引数の受け渡しと関数の先頭、つまりループに戻ります。

乾杯 & hth.,

于 2011-10-09T12:28:00.967 に答える
4

これは、while ループよりも関数呼び出しの方が時間がかかるためです。が非常に大きいかのように、最初の（再帰的ではない）を使用Nします。スタックがいっぱいになり、「スタックオーバーフロー」が発生する可能性があります:)

于 2011-10-09T11:51:30.047 に答える
4

あなたの最善の策は、階乗を明示的に計算しないことです。の Taylor (Maclaurin) 級数を計算する場合exp(x):

   exp(x) = 1 + x/1! + x^2/2! + x^3/3! + x^4/4! + ...

あなたの最善の策は、次のようなことをすることです：

   double y = 1.0;
   int i = 1;
   double curTerm = 1.0;
   double eps = 1e-10;  // whatever's desired
   while( fabs(curTerm) > eps)
   {
        curTerm *= x / (double)i;
        y += curTerm;
        ++i;
   }

このようにして、この問題には役に立たないほど急速に成長する階乗を明示的に計算する必要はありません。

于 2011-10-09T12:20:56.440 に答える
1

これは確かにデータ構造に関係しています。データ構造は面白いものです。データ サイズが小さい場合に優れたパフォーマンスを発揮するものもあれば、データ サイズが大きいほど優れたパフォーマンスを発揮するものもあります。

再帰コードには、現在の再帰の内容全体がスタックにプッシュされ、戻る途中でフェッチされる呼び出しスタックがあります。これは、各再帰呼び出しでの関数呼び出しの余分なオーバーヘッドです。そのため、パフォーマンスは遅いです。

詳細については、http: //publib.boulder.ibm.com/infocenter/iadthelp/v6r0/topic/com.ibm.etools.iseries.pgmgd.doc/c0925076137.htmを参照してください。

于 2011-10-09T11:52:59.377 に答える
0

関数呼び出しは、次の理由により、時間と空間の両方でより多くのコストがかかります。

  • 引数をスタックにプッシュし、戻り値をポップする必要があります。これには時間がかかります。
  • 各呼び出しは、スタックの独自の「フレーム」を消費します。
    • これは、非常に深い再帰を防ぐだけでなく (スタック サイズは通常数 MB に制限されています)、
    • また、キャッシュの局所性も損なわれ (呼び出しごとに RAM のさまざまな部分にヒットするため)、最終的には時間もかかります。

ところで、関数呼び出しは「操作が少ない」と言うとき、それは実際には真実ではありません。関数呼び出しはソース コードでは短く見えるかもしれませんが、何かの外観と実際の内部での動作には違いがあります。

また、この場合は関係ありませんが、「少ない操作」が必ずしもパフォーマンスの向上につながるとは限りません。場合によっては、「より多くの操作」を行いますが、ローカル性が向上すると、最新のすべての CPU が RAM レイテンシを隠すために実装するキャッシュとプリフェッチをより適切に利用できます。

于 2011-10-09T12:18:27.903 に答える