Function memory of JavaScript learning notes

This article mainly introduces the function memory of JavaScript study notes. The editor thinks it is quite good. Now I will share the JavaScript source code with you and give you a reference. If you are interested in JavaScript, please follow the editor to take a look.

This article explains the implementation of function memory and Fibonacci sequence and shares it with everyone. The details are as follows

Definition

Function memory refers to caching the last calculation result. When the next call is made, if the same parameters are encountered, the data in the cache will be returned directly.

For example:

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

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

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

Principle

It is very simple to implement such a memorize function. In principle, you only need to combine the parameters with the corresponding The result data is stored in an object. When called, it is judged whether the data corresponding to the parameter exists. If it exists, the corresponding result data is returned.

First version

Let’s write a version:

// 第一版 (来自《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)
  }
}

Let’s test it:

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;)

In In Chrome, using memorize takes about 60ms. If we don't use the functionmemory, it takes about 1.3 ms.

Note

What, we used the seemingly advanced function memory, but it turned out to be more time-consuming, almost 60 times in this example!

So, function memory is not omnipotent. If you look at this simple scenario, it is not suitable for function memory.

It should be noted that function memory is just a programming technique. It essentially sacrifices the space complexity of the algorithm in exchange for better time complexity. The code in client JavaScript Execution time complexity often becomes a bottleneck, so in most scenarios, this approach of sacrificing space for time to improve program execution efficiency is very desirable.

Second Edition

Because the first edition uses the join method, we can easily think that when the parameter is an object, the toString method will be automatically called. Convert it to [Object object], and then concatenate the string as the key value. Let’s write a demo to verify this problem:

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

var memoizedAdd = memorize(propValue)

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

Both return 1, which is obviously a problem, so let’s take a look at how underscore’s memoize function is implemented:

// 第二版 (来自 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;
};

From It can be seen from this implementation that underscore uses the first parameter of the function as the key by default, so if you use

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

var memoizedAdd = memorize(add)

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

directly, there must be a problem. If you want to support multiple parameters, we need to pass in the hasher function, since Define the stored key value. So we consider using 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

If you use JSON.stringify, the problem that the parameter is an object can also be solved, because the string after object serialization is stored.

Applicable scenarios

We take the Fibonacci sequence as an example:

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

We will find that the final count is 453, This means that the fibonacci function has been called 453 times! Maybe you are thinking, I just looped to 10, why was it called so many times, so let’s analyze it in detail:

When fib(0) is executed, it is called 1 time

When executing fib(1), it is called once

When executing fib(2), it is equivalent to fib(1) + fib(0) plus fib(2) itself this time, a total of 1 + 1 + 1 = 3 times

When executing fib(3), it is equivalent to fib(2) + fib(1) plus fib(3) itself this time, a total of 3 + 1 + 1 = 5 times

When executing fib(4), it is equivalent to fib(3) + fib(2) plus fib(4) itself this time, a total of 5 + 3 + 1 = 9 times

When When executing fib(5), it is equivalent to fib(4) + fib(3) plus fib(5) itself this time, a total of 9 + 5 + 1 = 15 times

When executing fib(6) , equivalent to fib(5) + fib(4) plus fib(6) itself this time, a total of 15 + 9 + 1 = 25 times

When executing fib(7), it is equivalent to fib(6 ) + fib(5) plus fib(7) itself this time, a total of 25 + 15 + 1 = 41 times

When executing fib(8), it is equivalent to fib(7) + fib(6) Adding fib(8) itself this time, a total of 41 + 25 + 1 = 67 times

When executing fib(9), it is equivalent to fib(8) + fib(7) plus fib(9) This time itself, a total of 67 + 41 + 1 = 109 times

When executing fib(10), it is equivalent to fib(9) + fib(8) plus fib(10) This time itself, a total of 109 + 67 + 1 = 177 times
So the total number of executions is: 177 + 109 + 67 + 41 + 25 + 15 + 9 + 5 + 3 + 1 + 1 = 453 times!

What if we use function memory?

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

We will find that the final total number of times is 12 times. Because of the use of function memory, the number of calls is reduced from 453 times to 12 times!

While you are excited, don’t forget to think: Why is it 12 times?

The results from 0 to 10 are stored once each. It should be 11 times? Hey, where did that extra time come from?

So we need to carefully look at our writing method. In our writing method, we actually overwrite the original fibonacci function with the generated fibonacci function. When we execute fibonacci(0), the function is executed once, and the cache is { 0: 0}, but when we execute fibonacci(2), we execute fibonacci(1) + fibonacci(0), because the value of fibonacci(0) is 0, !cache[address] The result If it is true, the fibonacci function will be executed again. It turns out that the extra time is here!

Perhaps you may feel that fibonacci is not used in daily development, and this example seems to have little practical value. In fact, this example is used to illustrate a usage scenario, that is, if a large number of repetitions are required For calculations, or where a large number of calculations depend on previous results, you can consider using function memory. And when you encounter this kind of scene, you will know it.

Related recommendations:

JavaScript function binding usage analysis

Detailed explanation of throttling and anti-shake debounce of JavaScript function

Explain how to use JavaScript function binding

The above is the detailed content of Function memory of JavaScript learning notes. For more information, please follow other related articles on the PHP Chinese website!