A function can cache the result of a previous operation in an object, and if the same argument is encountered the next time it is called, it returns the data directly from the cache, thus avoiding unnecessary recomputation. This optimization is called memory.

What is functional memory

A function can cache the result of a previous operation in an object, and if the same argument is encountered the next time it is called, it returns the data directly from the cache, thus avoiding unnecessary recomputation. This optimization is called memory.

Here’s an example:

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

// Assume memoize can implement function memory
let memoizeAdd = memoize(add);

memoizeAdd(1.2) / / 3
memoizeAdd(1.2) // The same argument is fetched from the cache a second time instead of recalculating
Copy the code

Memorization is just a programming trick that essentially sacrifices the spatial complexity of an algorithm for better time complexity. In client-side Javascript, the execution time complexity of code is often a bottleneck, so this sacrifice of space for time is very desirable in most cases.

Applicable scenario

Let’s say we want a recursive function to compute the Fibonacci sequence. A Fibonacci number is the sum of the previous two Fibonacci numbers. The first two arrays are 0 and 1.

let count = 0; // Record the number of function calls
let fibonacci = function(n){
    count ++ ; // Count + 1 each time the function is called
    return n < 2 ? n : fibonacci(n- 1) + fibonacci(n - 2);
}

for(let i = 0; i < 10; i++){
    console.log(`i=${i}: `,fibonacci(i))
}

console.log('Total times :',count)

// i=0:0
// i=1:1
// i=2:1
// i=3:2
// i=4:3
// i=5:5
// i=6:8
// i=7:13
// i=8:21
// i=9:34

// Total number: 276
Copy the code

The code above is fine by itself, but it does a lot of unnecessary work. We called Fibonacci 10 times in the for loop, but Fibonacci was actually called 276 times, and it called itself 266 times to evaluate something that might have just been evaluated. If we make the function memorizable, we can significantly reduce the amount of computation.

implementation

Now let’s think about how to implement a memoize function to help us construct functions with memory.

In principle, it is very simple, just the function parameters and corresponding results are cached in the closure, to be called to determine whether the data corresponding to the parameters exist, and directly return the cached data results.

The code implementation is as follows:

let memoize = function(fn){
    let cache = {};
    return function(. args){
        let key = JSON.stringify(args);
        if(! cache.hasOwnProperty(key)){ cache[key] = fn.apply(this,args);
        }
        return cache[key];
    };
}
Copy the code

In the above code, we converted the function argument to a JSON string to be used as the cache key, which basically guarantees that the exact key value can be obtained from the argument in each function call.

However, for some special parameters, such as undefined, NaN, Infinity, regular objects, functions, etc., the real key cannot be obtained after the json. stringify conversion.

Consider adding a function-type parameter to the memoize function, resolver, to pass the generation rules for cached keys to the user.

The implementation is as follows:

let memoize = function(fn,resolver){
    let cache = {};
    return function(. args){
        let key = typeof resolver === 'function' ? resolver.apply(this,args) :JSON.stringify(args);
        if(! cache.hasOwnProperty(key)){ cache[key] = fn.apply(this,args);
        }
        return cache[key];
    };
}
Copy the code

validation

Again, use the Fibonacci example to verify our completed memoize function.

Whether the number of function calls is reduced

let count = 0; // Record the number of function calls
let fibonacci = function(n){
    count ++ ; // Count + 1 each time the function is called
    return n < 2 ? n : fibonacci(n- 1) + fibonacci(n - 2);
}

fibonacci = memoize(fibonacci);

for(let i = 0; i < 10; i++){
    console.log(`i=${i}: `,fibonacci(i))
}

console.log('Total times :',count)

// i=0: 0
// i=1: 1
// i=2: 1
// i=3: 2
// i=4: 3
// i=5: 5
// i=6: 8
// i=7: 13
// i=8: 21
// i=9: 34

// Total count: 10
Copy the code

Whether the function call time is reduced

When memoize is not used, the Fibonacci function execution time is as follows when n is 30:

console.time('no memoize time');
fibonacci(30);
console.timeEnd('no memoize time');

// no memoize time: 10.919ms
Copy the code

When MEMOize is used, the Fibonacci function execution time is as follows when n is 30:

fibonacci = memoize(fibonacci);

console.time('memoize time');
fibonacci(30);
console.timeEnd('memoize time');

/ / memoize time: 0.331 ms
Copy the code

By comparison, it is very clear that the function call time is significantly reduced with memoize.

conclusion

  1. Function memory:
    • Let the function remember the arguments and the result of the processing
  2. Functions of memory:
    • To avoid repeated operations
  3. When to use function memory:
    • When a function may compute the same data repeatedly
  4. How to achieve:
    • Use closures to hold the calculated parameters and processing results

Like it? Don’t forget to give Mr. Voice a thumbs up 👍