Introduction to the usage of Memoization in JavaScript (code)

This article brings you an introduction to the usage of Memoization in JavaScript (code). It has certain reference value. Friends in need can refer to it. I hope it will be helpful to you.

memoization comes from the Latin memorandum ("to be remembered"), not to be confused with memorization.

First, let’s take a look at the description from Wikipedia:

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.

Simply put, memoization is an optimization technique mainly used to speed up computer programs by storing the results of expensive function calls and returning the cached results when the same inputs occur again.

This article first introduces a simple example of using memoization optimization technology, and then interprets the source code of using memoization in the underscore and reselect libraries to deepen understanding.

Factorial

Without using memoization

Without thinking, we will immediately write the following code:

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

Use 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
    }
};

Using closures and memoization

The common way is to use closures and memoization together:

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

Continuing to deform, the following writing method 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
});

From this example of factorial, we can know that memoization is a method of exchanging space for time. It stores the execution results. The next time the same input occurs, the results will be directly output, which improves the execution speed.

underscore The memoization in the source code

// 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;
};

The code is clear at a glance. Using _.memoize to implement factorial is as follows:

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

Refer to this source code, the factorial above It can continue to be transformed 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
});

reselect memoization in the source code

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

From the source code, we can know that when lastArgs is the same as arguments, func will not be executed again.

Summary

memoization is an optimization technology that avoids unnecessary repeated calculations and can improve calculation speed.

The above is the detailed content of Introduction to the usage of Memoization in JavaScript (code). For more information, please follow other related articles on the PHP Chinese website!