JavaScriptの関数記憶学習メモ-jsチュートリアル-php.cn

JavaScriptの関数記憶学習メモ

韦小宝

リリース： 2018-01-25 11:03:04

オリジナル

1570 人が閲覧しました

この記事は主に JavaScript の関数メモリを紹介するもので、編集者が非常に優れていると思ったので、参考として JavaScript のソースコードを共有します。 JavaScript に興味がある方は、エディターをフォローして見に来てください

この記事では、関数メモリとフィボナッチ数列の実装を説明し、皆さんと共有します。詳細は次のとおりです

定義

メモリは、計算結果がキャッシュされた最後の時間を指します。次の呼び出しが行われるときに、同じパラメータが見つかった場合、キャッシュ内のデータが直接返されます。

例:

function add(a, b) {
  return a + b;
}

// 假设 memorize 可以实现函数记忆
var memoizedAdd = memorize(add);

memoizedAdd(1, 2) // 3
memoizedAdd(1, 2) // 相同的参数，第二次调用时，从缓存中取出数据，而非重新计算一次

ログイン後にコピー

Principle

原則として、呼び出し時にパラメータと対応する結果データをオブジェクトに保存するだけで済みます。パラメータに対応するデータが存在する場合、対応する結果データが返されます。

最初のバージョン

バージョンを書いてみましょう:

// 第一版 (来自《JavaScript权威指南》)
function memoize(f) {
  var cache = {};
  return function(){
    var key = arguments.length + Array.prototype.join.call(arguments, ",");
    if (key in cache) {
      return cache[key]
    }
    else return cache[key] = f.apply(this, arguments)
  }
}

ログイン後にコピー

テストしてみましょう:

var add = function(a, b, c) {
 return a + b + c
}

var memoizedAdd = memorize(add)

console.time(&#39;use memorize&#39;)
for(var i = 0; i < 100000; i++) {
  memoizedAdd(1, 2, 3)
}
console.timeEnd(&#39;use memorize&#39;)

console.time(&#39;not use memorize&#39;)
for(var i = 0; i < 100000; i++) {
  add(1, 2, 3)
}
console.timeEnd(&#39;not use memorize&#39;)

ログイン後にコピー

Chromeでは、memoryを使用すると約60ミリ秒かかります関数を使用しない場合メモリは約1.3ミリ秒かかります。。

注意

なんと、一見高度な関数メモリを使用しましたが、実際にはさらに時間がかかり、この例では約 60 回も使用されていることが判明しました。

つまり、この単純なシナリオを見ると、関数メモリは万能ではありません。実際には、関数メモリの使用には適していません。

関数メモリは単なるプログラミングテクニックであることに注意してください。クライアント側の JavaScript では、コードの実行時間の複雑さがボトルネックになることがよくあります。したがって、ほとんどのシナリオでは、時間のためにスペースを犠牲にしてプログラムの実行効率を向上させるこのアプローチが非常に望ましいです。

2 番目のバージョン

最初のバージョンでは join メソッドが使用されているため、パラメーターがオブジェクトの場合、自動的に toString メソッドを呼び出して [Object オブジェクト] に変換し、それを結合すると簡単に考えることができます。 stringをキー値として使用します。この問題を検証するデモを書いてみましょう:

var propValue = function(obj){
  return obj.value
}

var memoizedAdd = memorize(propValue)

console.log(memoizedAdd({value: 1})) // 1
console.log(memoizedAdd({value: 2})) // 1

ログイン後にコピー

どちらも 1 を返しますが、これは明らかに問題です。そこで、アンダースコアのメモ化関数がどのように実装されているかを見てみましょう:

// 第二版 (来自 underscore 的实现)
var memorize = function(func, hasher) {
  var memoize = function(key) {
    var cache = memoize.cache;
    var address = &#39;&#39; + (hasher ? hasher.apply(this, arguments) : key);
    if (!cache[address]) {
      cache[address] = func.apply(this, arguments);
    }
    return cache[address];
  };
  memoize.cache = {};
  return memoize;
};

ログイン後にコピー

この実装からわかるように、アンダースコアのデフォルトは関数の最初のパラメータをキーとして使用するため、

var add = function(a, b, c) {
 return a + b + c
}

var memoizedAdd = memorize(add)

memoizedAdd(1, 2, 3) // 6
memoizedAdd(1, 2, 4) // 6

ログイン後にコピー

を直接使用すると、間違いなく問題が発生します。複数のパラメータをサポートしたい場合は、ハッシュ関数を渡して、保存されたキーの値をカスタマイズする必要があります。そこで、JSON.stringify の使用を検討します。

var memoizedAdd = memorize(add, function(){
  var args = Array.prototype.slice.call(arguments)
  return JSON.stringify(args)
})

console.log(memoizedAdd(1, 2, 3)) // 6
console.log(memoizedAdd(1, 2, 4)) // 7

ログイン後にコピー

JSON.stringify を使用すると、オブジェクトのシリアル化後の文字列が保存されるため、パラメータがオブジェクトであるという問題も解決できます。

適用可能なシナリオ

フィボナッチ数列を例として取り上げます:

var count = 0;
var fibonacci = function(n){
  count++;
  return n < 2? n : fibonacci(n-1) + fibonacci(n-2);
};
for (var i = 0; i <= 10; i++){
  fibonacci(i)
}

console.log(count) // 453

ログイン後にコピー

最終的なカウントは 453 であることがわかります。これは、フィボナッチ関数が 453 回呼び出されたことを意味します。おそらく、10 までループしただけなのに、なぜ何度も呼び出されたのかと考えているかもしれません。それでは、詳しく分析してみましょう:

fib(0) が実行されるとき、それは 1 回呼び出されます

fib(1) が実行されるとき, 1回呼び出されます

fib(2)を実行すると、今回はfib(1)+fib(0)+fib(2)そのもの、合計1+1+1=3回に相当します

実行時fib(3)、今回は fib(2) + fib(1) に fib(3) そのものを加えたものと等しく、合計 3 + 1 + 1 = 5 回になります

fib(4) を実行すると、今回は fib(3) + fib(2) + fib(4) 自体に相当、合計 5 + 3 + 1 = 9 回

fib(5) を実行すると、fib(4) + fib に相当(3) プラス fib(5) 今回自体は、合計 9 + 5 + 1 = 15 回

fib(6) を実行すると、 fib(5) + fib(4) プラス fib(6) と等価になります今回はそれ自体、合計15 + 9 + 1 = 25回

fib(7)を実行すると、今回はfib(6) + fib(5) + fib(7)自体を加えた合計25回に相当します+ 15 + 1 = 41 回

fib(8 ) を実行すると、今回は fib(7) + fib(6) と fib(8) 自体を足したことになり、合計 41 + 25 + 1 = 67 回

fib(9)を実行すると、今度はfib(8)+fib(7)+fib(9)そのもの、計67+41+1=109回に相当

fib(10)を実行した場合、 fib(9) + fib(8) + fib(10) に相当します。今回自体は、合計 109 + 67 + 1 = 177 回です
つまり、合計実行回数は、177 + 109 + 67 となります。 + 41 + 25 + 15 + 9 + 5 + 3 + 1 + 1 = 453 回!

関数メモリを使用するとどうなるでしょうか?

rreee

関数メモリの使用により、呼び出し回数が 453 回から 12 回に減少することがわかります

興奮している間、忘れないでください。なぜ 12 倍なのでしょうか?

0から10までの結果を1回保存すると、11回になるはずです?ねえ、その余分な時間はどこから来たのですか？

そのため、書き込み方法を注意深く検討する必要があります。この書き込み方法では、実際に fibonacci(0) を実行すると、関数が 1 回実行され、キャッシュが {0 になります。 : 0} ですが、fibonacci(2) を実行すると、fibonacci(1) + fibonacci(0) が実行されます。fibonacci(0) の値が 0 であり、 !cache[address] の結果が true であるため、fibonacci 関数が実行されます。また。延長戦がここにあることが判明しました！

おそらく、フィボナッチは日常の開発では使用されず、この例は実用的な価値が低いように思われるかもしれません。実際、この例は、使用シナリオ、つまり、大量の繰り返し計算が必要な場合を説明するために使用されています。、または多数の計算が以前の結果に依存する場合は、関数メモリの使用を検討できます。そして、このような場面に遭遇すると、それがわかります。