JavaScript 関数の概要

この記事はJavaScriptの学習メモの関数メモリを中心に紹介していますが、編集者がとても良いと思ったので、参考としてシェアさせていただきます。エディターと一緒に覗いてみてください

この記事では関数メモリとフィボナッチ数列の実装について説明し、皆さんと共有します

定義

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

例:

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

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

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

原則

このような記憶関数を実装する必要があるのは、呼び出し時にパラメータと対応する結果データをオブジェクトに保存することだけです。に対応するパラメータを判定し、データが存在するかどうかを判断し、存在する場合は対応する結果データを返します。

最初のバージョン

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

// 第一版 (来自《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('use memorize')
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を使用しない場合、memoryを使用すると約60ミリ秒かかります。約1.3ミリ秒。

注意

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

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

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

2 番目のバージョン

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

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 = '' + (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 回!

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

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

fibonacci = memorize(fibonacci)

for (var i = 0; i <= 10; i++) {
  fibonacci(i)
}

console.log(count) // 12

関数メモリを使用しているため、呼び出し回数は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 関数が実行されます。また。延長戦がここにあることが判明しました！

もう 1 つ

おそらく、この例は、使用シナリオを説明するために使用されています。多数の繰り返し計算が必要な場合、または多数の計算が以前の結果に依存する場合は、関数メモリの使用を検討できます。そして、このような場面に遭遇すると、それがわかります。

以上がJavaScript 関数の概要の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。