Introduction to JavaScript functions

This article mainly introduces the function memory of JavaScript learning notes. The editor thinks it is quite good. Now I will share it with you and give it as a reference. Let’s follow the editor and 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, only the parameters and corresponding result data need to be stored in an object. When calling, it is judged whether the data corresponding to the parameter exists, and 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 out ：

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 Chrome, using memorize takes about 60ms. If we don't use function memory, 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 actually not suitable for using 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. In client-side JavaScript, the execution time complexity of the code often becomes 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 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 see 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;
};

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

# directly ##

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

var memoizedAdd = memorize(add)

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

There must be a problem. If we want to support multiple parameters, we need to pass in the hasher function and customize 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 serialized characters of the object are stored. string.

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 You will find that the final count is 453, which 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!

One more thing

Maybe you will feel that fibonacci is not used in daily development. This example feels that it is not of high practical value. In fact, this The example is used to illustrate a usage scenario, that is, if a large number of repeated calculations are required, or 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.

The above is the detailed content of Introduction to JavaScript functions. For more information, please follow other related articles on the PHP Chinese website!