5

JavaScript に変換できる言語で作業しています。一部のスタック オーバーフローを回避するために、特定の関数を for ループに変換してテール コールの最適化を適用しています。驚くべきことは、変換が再帰バージョンよりも速くないことです。

http://jsperf.com/sldjf-lajf-lkajf-lkfadsj-f/5

再帰バージョン:

(function recur(a0,s0){
    return a0==0 ? s0 : recur(a0-1, a0+s0)
})(10000,0)

テール コールの最適化後:

ret3 = void 0;
a1   = 10000;
s2   = 0;
(function(){
    while (!ret3) {
        a1 == 0 
            ? ret3     = s2
            : (a1_tmp$ = a1 - 1 ,
               s2_tmp$ = a1 + s2,
               a1      = a1_tmp$,
               s2      = s2_tmp$);
     }
})();
ret3;

Google Closure Compiler を使用してクリーンアップした後:

ret3 = 0;
a1   = 1E4;
for(s2 = 0; ret3 == 0;)
    0 == a1 
        ? ret3     = s2 
        : (a1_tmp$ = a1 - 1 ,
           s2_tmp$ = a1 + s2,
           a1      = a1_tmp$,
           s2      = s2_tmp$);
c=ret3;

再帰的なバージョンは、「最適化された」バージョンよりも高速です! 再帰バージョンが何千ものコンテキスト変更を処理する必要がある場合、これはどのように可能になるのでしょうか?

4

3 に答える 3

5

テールコールの最適化以上の最適化があります。

たとえば、必要なのは次の 2 つの一時変数を使用していることに気付きました。

s2 += a1;
a1--;

これだけで実質的に操作数が 3 分の 1 に減り、パフォーマンスが 50% 向上します。

長期的には、操作自体を最適化する前に、実行されている操作を最適化することが重要です。

編集：これは更新されたjsperfです

于 2013-10-05T22:32:00.923 に答える
2

recur名前付き関数はそれ自体のスコープに含まれているrecur/同じスコープを共有しているため、再帰バージョン内でのコンテキストの変更は予想ほど多くありません。その理由は、JavaScript エンジンがスコープを評価する方法に関係しており、このトピックについて説明している Web サイトがたくさんあるので、ここでは説明しません。もう一度見てみるとrecur、これはいわゆる「純粋な」関数でもあることがわかります。これは、基本的に、内部実行が実行されている限り (簡単に言えば、値が返されるまで) 自身のスコープを離れる必要がないことを意味します。これら2つの事実により、基本的に高速になります。ここで言及したいのは、最初の例は、3 つすべての中で最適化された唯一の末尾呼び出しです。tc 最適化は再帰関数でのみ実行でき、これが唯一の再帰関数です。

ただし、2 番目の例 (しゃれた意図はありません) をもう一度見てみると、「オプティマイザー」が操作を分割することによって以前の純粋な関数にスコープを導入したため、事態が悪化したことがわかります。

  • 引数の代わりに変数
  • whileループ_
  • 導入された内部変数と外部変数を分離する IIFE (即時に呼び出される関数式)

これは、エンジンが 10000 のコンテキスト変更を処理する必要があるため、パフォーマンスの低下につながります。

実を言うと、3 番目の例が再帰的な例よりもパフォーマンスが低い理由がわかりません。

  • 使用しているブラウザ (別のブラウザを試して結果を比較したことはありますか?)
  • 変数の数
  • for ループによって作成されたスタック フレーム (聞いたことはありません)。これは、最初の例と関係があります。JS エンジンは、return ステートメントが見つかるまで、純粋な再帰関数を解釈します。ステートメントに続く最後のものが関数呼び出しである場合、引数として渡す式 (存在する場合) と変数を評価し、関数を呼び出してフレームを破棄します。
  • 何か、ブラウザベンダーだけが本当にあなたに伝えることができます:)
于 2015-04-01T16:39:39.000 に答える
2

Kolinkが言うように、あなたのコードは単純に合計に追加しn、1減らし、到達しないまでnループしますn0

そうするだけです：

n = 10000, o = 0; while(n) o += n--;

再帰バージョンよりも高速で読みやすく、もちろん同じ結果を出力します

于 2013-10-06T00:04:46.643 に答える