Memoization comes from the Latin memorandum (“to be remembered”) and is not to be confused with memorization.

First, take a look at wikipedia’s description:

In computing, memoization or memoisation is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.

In simple terms, Memoization is an optimization technique primarily used to speed up computer programs by storing the results of expensive function calls and returning cached results if the same input occurs again.

This article begins with a simple example of using Memoization optimization techniques, and then highlights and ResELECT libraries that use Memoization for a deeper understanding.

factorial

Do not use the memoization

Without thinking, we would immediately write the following code:

const factorial = n => {
    if (n === 1) {
        return 1
    } else {
        return factorial(n - 1) * n
    }
};Copy the code

The use of memoization

const cache = []
const factorial = n => {
    if (n === 1) {
        return 1
    } else if (cache[n - 1]) {
        return cache[n - 1]
    } else {
        let result = factorial(n - 1) * n
        cache[n - 1] = result
        return result
    }
};Copy the code

Use closures and memoization

A common way to do this is with closures and memoization:

const factorialMemo = () => { const cache = [] const factorial = n => { if (n === 1) { return 1 } else if (cache[n - 1])  { console.log(`get factorial(${n}) from cache... `) return cache[n - 1] } else { let result = factorial(n - 1) * n cache[n - 1] = result return result } } return factorial }; const factorial = factorialMemo();Copy the code

Keep morphing. The following is the most common form.

const factorialMemo = func => { const cache = [] return function(n) { if (cache[n - 1]) { console.log(`get factorial(${n}) from cache... `) return cache[n - 1] } else { const result = func.apply(null, arguments) cache[n - 1] = result return result } } } const factorial = factorialMemo(function(n) { return n === 1 ? 1 : factorial(n - 1) * n });Copy the code

From the example of factorial, we can know that memoization is a way of replacing time with space to store the execution results, and the same input will directly output the results the next time, which improves the execution speed.

Memoization in the underscore source

// Memoize an expensive function by storing its results. _.memoize = function(func, hasher) { var memoize = function(key) { var cache = memoize.cache; var address = '' + (hasher ? hasher.apply(this, arguments) : key); if (! _.has(cache, address)) cache[address] = func.apply(this, arguments); return cache[address]; }; memoize.cache = {}; return memoize; };Copy the code

Memoize the code at a glance, using _.memoize to implement the factorial as follows:

const factorial = _.memoize(function(n) {
    return n === 1 ? 1 : factorial(n - 1) * n
});Copy the code

With reference to the source code, the factorial above can continue to be deformed as follows:

const factorialMemo = func => { const memoize = function(n) { const cache = memoize.cache if (cache[n - 1]) { console.log(`get factorial(${n}) from cache... `) return cache[n - 1] } else { const result = func.apply(null, arguments) cache[n - 1] = result return result } } memoize.cache = [] return memoize } const factorial = factorialMemo(function(n) { return n === 1 ? 1 : factorial(n - 1) * n });Copy the code

Memoization in resELECT source

export function defaultMemoize(func, equalityCheck = defaultEqualityCheck) { let lastArgs = null let lastResult = null // we reference arguments instead of spreading them for performance reasons return function () { if (! areArgumentsShallowlyEqual(equalityCheck, lastArgs, arguments)) { // apply arguments instead of spreading for performance. lastResult = func.apply(null, arguments) } lastArgs = arguments return lastResult } };Copy the code

We know from the source that func is no longer executed when lastArgs is the same as arguments.

conclusion

Memoization is an optimization technique that avoids some unnecessary double calculations and can increase computation speed.

reference

  1. Memoization wiki
  2. Understanding JavaScript Memoization In 3 Minutes
  3. Underscore
  4. reselect
  5. Implementing Memoization in JavaScript