JavaScript メモ化により関数にメモリを持たせることが可能 function

JavaScript メモ化により関数にメモリを持たせることが可能 function_javascript スキル

WBOY

リリース： 2016-05-16 18:00:09

オリジナル

1107 人が閲覧しました

フィボナッチ数列を計算するための再帰関数が必要だとします。フィボナッチ数は、前の 2 つのフィボナッチ数の合計です。最初の 2 つの数字は 0 と 1 です。

コードをコピーコードは次のとおりです。

 
var fibonacci = function (n) { 
return n 
for (var i = 0; i document.writeln('// ' i ': ' fibonacci(i)) 
} 

// 0: 0 
// 1: 1 
/ / 2: 1 
// 3: 2 
// 4: 3 
// 5: 5 
// 6: 8 
// 7: 13 
// 8 : 21 
// 9: 34 
// 10: 55 

 

これは機能しますが、多くの不必要な作業が行われます。フィボナッチ関数は 453 回呼び出されています。これを 11 回呼び出し、計算されたばかりの値を計算するために自分自身を 442 回呼び出しました。この関数をメモリ対応にすると、計算の複雑さを大幅に軽減できます。

保存された結果は、memo という配列に保存されます。保存された結果はクロージャで隠すことができます。関数が呼び出されると、関数はまず計算結果が既知であるかどうかを確認し、既知であれば、保存されている結果をすぐに返します。

コードをコピーコードは次のとおりです。

var fibonacci = function() { 
var memo = [0, 1]; 
var fib = function (n) { 
var result = memo[n]; 
if (typeof result !== 'number') { 
結果 = fib (n - 1) fib(n - 2); 
メモ [n] = 結果 
}; (); 

 
この関数は同じ結果を返しますが、呼び出されるのは 29 回だけです。以前に保存された結果を取得するために、それを 11 回呼び出し、さらに 18 回自分自身を呼び出しました。 
上記の内容は http://demon.tw/programming/javascript-memoization.html からのものです。

realazy はブログで JavaScript メモ化の実装を説明しました。メモ化は関数の戻り値のキャッシュです。関数のパラメータと戻り値を 1 対 1 で対応させるハッシュ リストなど、実際には wiki に詳細な説明があります。ここでは、実際のコードについてのみ説明します。この記事では、クエリ キャッシュ結果のキーとして文字列が使用されている場合、パラメータに一意のキーを確保することが難しいなどの問題があります。 1 階のコメントに記載されている [221,3] や [22,13] など。 

まず、キャッシュされたデータを保存するためにハッシュテーブルを使用します。

コードをコピーします。

コードは次のとおりです。 ( var i=0 , l = argument.length; i < l; i ) key.push(arguments[i]); if( !(キャッシュ内のキー) ) cache[key ] = fn.apply (this, argument); return queue[key] }

 
違いは、配列を直接使用することです。キーですが、関数に注意してください。 の引数は、実際の配列ではなく、js インタープリターによって実装された特別なオブジェクトであるため、変換する必要があります... 
ps: 元のパラメーターには、メソッド名とコンテキスト参照が含まれています。 fib.fib_memo = Memoize('fib_memo', fib) ですが、実際にはこれを使用して、カリー化によって生成された関数の上位レベルのオブジェクトを直接参照できます。より複雑な例については、John Resig の makeClass を参照してください。関数参照を直接渡すように変更しました: fib.fib_memo = Memoize(fib.fib_memo) 
このように書くと、パラメータで構成される配列は非常に信頼性が高いように思えます。しかし実際には、配列が js オブジェクトの属性名として使用できる理由は、関数に渡すパラメーターが次のような場合、配列が文字列として扱われるためです。 ,3), キャッシュ オブジェクトは次のようになります: { “1,2,3″: somedata } (1,2,{i:”yy”}) などのオブジェクトがある場合。実際のキー値は「1,2,[object Object]」となるため、これは実際には配列を文字列に結合する方法と何ら変わりません... 
例: 

コードをコピーします

 コードは次のとおりです:

var a = [1,2,{yy:'0'}]; >var b = [1,2,{xx :'1'}];
var obj = {};
obj[a] = "111"; ;
for( var i in obj )

alert( i " = " obj[i] ); //「1,2,[object Object] = 222」のみが表示されます、obj[a] = 「111」が上書きされます
パラメータをキー名として直接使用する方法は信頼できません...別の方法を試してください:

コードをコピーコードは次のとおりです。

 
function Memoize(fn){ 
var queue = {}, args = []; 
return function(){ 
for( var i= 0, key = args.length; i < key; i ) { 
if(equal(args[i], argument ) ) 
return キャッシュ[i]; 
args[key] =引数; 
キャッシュ[キー] = fn.apply(this, argument); 
キャッシュを返す 
}; 

 
 は完全に上記の問題を回避するには、ハッシュ キーと値のペア インデックスを使用する代わりに、関数のパラメーターと結果がそれぞれ 2 つのリストにキャッシュされ、比較のために最初にパラメーター リスト全体が走査され、対応するキー名/ID 番号が調べられます。が見つかった場合は、結果リストからデータを取得します。以下は配列を比較するための等価メソッドです: 

コードをコピーコードは次のとおりです:

functionequal( first , Second ){

if( !first || !second || first.constructor != Second.constructor ) 
return false; 
if( first.length && typeof first != "string" ) 
for(var i=0, l = ( first.length > Second.length ) ? first.length : Second.length; iif( !equal( first[i], Second[i] ) ) return false; 
} 
else if( typeof first == 'object' ) 
for(var n in first){ 
if( !equal ( first[n] , Second[n] ) ) return false; 
} 
else 
return ( first === Second ); 

 
thousand 引数と args の配列を比較するために == を直接使用しないでください。パラメータの内容ではなくメモリ参照が比較されるためです。 
このメソッドは非常に遅く、等しいメソッドは実際にはほとんど影響を与えません。しかし、キャッシュされた結果の数が増えると、毎回パラメーター リストを走査するのは非常に非効率的です (Firefox3 では 80 を超えるフィボナッチ数列を見つけます)。 Safari3) と比較して約 40 ミリ秒かかります。 
パラメータがあまり変更されない場合、または実際のアプリケーションでパラメータを受け入れない場合は、Oliver Steel の記事「One-Line JavaScript Memoization」を参照して、短い関数で問題を解決できます。 style. : 

コードをコピーします

コードは次のとおりです: function Memoize(o, p) ) { var f = o[p], mf, 値;

var s = function(v) {return o[p]=v||mf}; {

( s(function(){return value})).reset = mf.reset; 
return value = f.apply(this,arguments); //これはパラメータを受け入れられるように変更されました。 
}).reset = s)(); 
} 

 
例: 

コードをコピー

コードは次のとおりです。 var fib = { temp: function(n){ for(var i=0;in=n 2;

 return n; 
} 
} 
Memoize(fib,"temp"); // fib.temp に戻り値をキャッシュさせます
fib.temp( 16); //実行結果: 20006、キャッシュ
fib.temp(20) //実行結果: 20006 
fib.temp(10); .reset(); //キャッシュをリセット
fib.temp(10) //実行結果: 20010 

 