This is the fifth day of my participation in the August More text Challenge. For details, see:August is more challenging

1. What is a memory function

Memorization is the process of building a function so that it can remember the last calculation. In simple terms, save the parameters of each call and the result of the function run, the next time the function is called with the same parameters, you can directly return the saved result, without the need to redo the complex calculation, which avoids repeated complex calculation, can significantly improve the performance.

2. How to implement memory function

Since you are saving the parameters and the corresponding results, it must be the address to save (the repository) and the key to open the repository (the method that can access the address). However, if you put the repository of results in a function, each call will create a new repository, and if you define global variables, it is easy to be polluted by the outside world. So we can do this with a closure that holds a reference to the variable so that it can’t be released by the garbage collector

2. Advantages and disadvantages of memory functions

Memory functions retain references to variables by forming closures, and can be used to improve performance in recursive functions that require a large number of repeated calculations. However, its defects are also particularly obvious. It is a space-for-time method, and only functions that are executed multiple times and once can be memorized, and functions cannot have side effects. In some simple calculation function does not need to use this function, according to a little chicken ribs, after all, I also used in the project), and memory function is difficult to do the load test or estimate algorithm complexity, because the test results depends on the function before operation, I think the most important thing is to learn programming thinking this.

4. Case study: Calculate factorial

Ordinary function function:

The function of the factorial (num) {count++ if (num = = = 0 | | num = = = 1) {/ / 0 factorial is the factorial of 1 1 1 return 1; } return num * factorial(num-1); } for(let i = 1 ; i <=5 ; i++){ console.log(factorial(i)); } console.log(" count ",count);Copy the code

Factorial means multiplying 1 times 2 times 3 times 4 all the way to the desired number: then:

1! = 1 => Number 1

2! = 2*1 => number 2

3! = 321 => Times 3

4! = 4 * 3 * 2 * 1 => 4

5! = 5 * 4 * 3 * 2 * 1 => 5

So count = 1+2+3+4+5 = 15

And we can see that if we want 5 factorial we only need 4 factorial5 is fine. I need 4 factorial and I only need 3 factorial4, and we need to start over each time we call this method. So we can save the previous results.

Function factorial(num){count++ if(cache[num]){return cache[num]}else{ if(num === 0 || num === 1){ cache[0] = 1 cache[1] = 1 return 1 }else{ cache[num] = num * factorial(num-1) return cache[num] } } } for(let i = 1 ; i <=5 ; i++){ console.log(factorial(i)); } console.log(" count ",count);Copy the code

So now count should be calculated as:

1! = 1 => Number 1

2! * 1 = 2! = > the number 2

3! = 3 * 2! = > the number 2

4! = 4 * 3! = > the number 2

5! = 5 * 4! = > the number 2

So count = 1+2+2+2+2 = 9

All the factorials except 1 are the factorials of the last number times the number itself, and the previous factorials have been saved, so they’re all 2

The first is that the cache variable we defined is not safe because it can be contaminated (count is only used for testing data). The second thing is that if we write it this way, every time we want to make the function memorize, we’re going to have to reinvent the function, so we’re going to write a function that memorizes the function; Third, the example above uses an array just because the factorial parameter is of type number. We use the index to access the corresponding value in the array, but there is no guarantee that all other memory functions are of type number.

Function encodes (fn) {const cache = {} return function() {// generate a unique key, And it has to do with the parameters of the function // it has to be able to get the key based on the parameters of the particular algorithm. You can also customize other algorithm) const key = the arguments. The length + Array. Prototype. Join. Call (the arguments) if (cache [key]) {return cache [key] }else{// The reason to use apply is because fn's arguments are not fixed or unknown, and // because apply can use argument (or arraylike objects, Return cache[key] = fn. Apply (this,arguments) return cache[key]}}}Copy the code

** Now that we have a function that encodes the function, the factorial above can be changed to: **

Const fn = enbom (factorial)

Memory functions, while improving performance, are typically space-for-time, and must be pure functions with no side effects. Use them with caution (the fact that computers perform so well these days)