[この記事のアドレス] http://cuimingda.com/2009/02/speed-up-your-javascript-part-3.html
再帰は、スクリプトの実行速度を低下させる敵の 1 つです。再帰が多すぎると、ブラウザーの動作がどんどん遅くなり、最終的にブラウザーが停止したり、突然不可解に自動的に終了したりするため、この一連のパフォーマンスの問題を JavaScript で解決する必要があります。このシリーズの 2 番目の記事では、メモ化テクノロジを使用して関数内の多すぎる再帰呼び出しを置き換える方法を簡単に紹介しました。メモ化は、以前の計算結果をキャッシュして、すでに計算された結果を再計算する必要がないようにする手法です。再帰によって計算を実行する関数の場合、メモ化は非常に便利です。私が現在使用しているメモライザーは Crockford によって書かれたもので、主に整数を返す再帰操作で使用されます。もちろん、すべての再帰関数が整数を返すわけではないため、より多くの種類の再帰関数を処理するには、より一般的な memoizer() 関数が必要です。
function memoizer(fundamental, キャッシュ){ キャッシュ = キャッシュ || {} var シェル = function(arg){ if (!(キャッシュ内の引数)){ キャッシュ[引数] = 基本(シェル, 引数) } キャッシュ[引数]を返します; }; return shell;} このバージョンの関数は、Crockford によって作成されたものとは少し異なります。まず、パラメーターの順序が逆になり、元の関数が最初のパラメーターとして設定され、2 番目のパラメーターはキャッシュ オブジェクトになります。すべての再帰関数に初期情報が含まれているわけではないため、これはオプションです。このバージョンが整数を返さない再帰関数に対応できるように、関数内でキャッシュ オブジェクトの型を配列からオブジェクトにキャストしました。シェル関数では、in 演算子を使用して、パラメータがすでにキャッシュに含まれているかどうかを判断します。未定義は有効な戻り値であるため、この記述方法は、型が未定義でないことをテストするよりも安全です。説明するために、引き続き前述のフィボナッチ数列を使用します:
var fibonacci = memoizer(function (recur, n) { return recur(n - 1) + recur(n - 2); }, {"0": 0, "1" :1}); 同様に、関数 fibonacci(40) を実行すると、元の関数は 331,160,280 回呼び出されるのではなく、40 回だけ呼び出されます。メモ化は、厳密に定義された結果セットを使用する再帰アルゴリズムに最適です。ただし、メモ化手法を使用した最適化に適していない再帰的アルゴリズムは実際に数多くあります。
学校の教授の一人は、再帰が使用される状況はすべて、必要に応じて反復に置き換えることができると常に主張していました。実際、再帰と反復は、特にもう一方が失敗した場合に、お互いを補う方法としてよく使用されます。再帰的アルゴリズムを反復的アルゴリズムに変換するテクノロジーも、開発言語には依存しません。ただし、実行環境のリソースが非常に制限されているため、JavaScript の重要性はさらに高くなります。マージ ソートなどの一般的な再帰アルゴリズムを見てみましょう。このアルゴリズムを JavaScript で実装するには、次のコードが必要です。
function merge(left, right){ var result = [] while (left.length > 0 && right.length > 0) { if (left[0] < right[0]){ result.push(left.shift()); } else { result.push(right.shift()) } } return result.concat(left ).concat (right);}//マージ並べ替えアルゴリズム function mergeSort(items){ if (items.length == 1) { return items; } var middle = Math.floor(items.length / 2) 再帰を使用し、 left = items. lice(0, middle), right = items.slice(middle); return merge(mergeSort(left), mergeSort(right));} mergeSort() 関数を呼び出して配列を処理すると、ソートされた配列を返すことができます。 mergeSort() 関数が呼び出されるたびに、2 つの再帰呼び出しが行われることに注意してください。このアルゴリズムは、メモ化を使用して最適化することはできません。各結果が計算されて使用されるのは 1 回だけであり、結果をバッファリングしても役に立たないからです。 100 要素の配列に対して mergeSort() 関数を使用すると、合計 199 回の呼び出しが行われます。 1000 要素の配列は 1999 回の呼び出しを実行します。この場合の解決策は、再帰アルゴリズムを反復アルゴリズムに変換することです。これは、いくつかのループを導入することを意味します (アルゴリズムについては、この記事「リスト処理: 自然に並べ替える」を参照してください)。
// 反復実装を使用します。マージソートアルゴリズム関数 mergeSort(items){ if (items.length == 1) { return items; } var work = []; for (var i=0, len=items.length; i < len; i++){ work .push([items[i]]); } work.push([]); //項目数が奇数の場合 (var lim=len; lim > 1; lim = (lim+1)/2 ) { for (var j=0,k=0; k < lim; j++, k+=2){ work[j] = merge(work[k], work[k+1]) } work[j] = [ ]; //項目数が奇数の場合 } return work[0];}このマージソートアルゴリズムの実装では、ソートに再帰ではなく一連のループが使用されます。マージ ソートではまず配列が 1 つの要素のみを含む複数の配列に分割されるため、このメソッドは再帰関数を使用して暗黙的にこの操作を実行するのではなく、より明示的にこの操作を実行します。作業配列は、1 要素配列の配列を含むように初期化されます。ループ内で毎回、2 つの配列がマージされ、マージされた結果が作業配列に戻されます。関数が実行されると、ソートされた結果が作業配列の最初の要素を通じて返されます。マージ ソートのこの実装では、アルゴリズムも再帰を使用せずに実装されます。ただし、これにより大量のループが発生し、ループの数は並べ替えられる配列内の要素の数に基づいているため、この追加のオーバーヘッドに対処するには、前の記事で説明した手法を使用してループを変更する必要がある場合があります。 。
基本原則を要約すると、再帰を使用するときは常に注意する必要があります。メモ化と反復は、再帰を置き換える 2 つのソリューションです。当然、最も直接的な結果は、スクリプトが制御不能になることを促すダイアログ ボックスを回避することです。