资讯专栏INFORMATION COLUMN

上云采购季！| 2核2G4M爆款云服务器低至59元/年，更有多台、长期优惠，快来选购！

立即前往
首页/文章专栏/JavaScript 高级技巧 Memoization

JavaScript 高级技巧 Memoization

刘德刚 / 1664人阅读

摘要：来源于拉丁语，不要与混淆了。本文首先介绍一个简单的使用优化技术的例子，然后解读和库中使用的源码，加深理解。总结是一种优化技术，避免一些不必要的重复计算，可以提高计算速度。

memoization 来源于拉丁语 memorandum ("to be remembered")，不要与 memorization 混淆了。

首先来看一下维基百科的描述：

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.

简单来说，memoization 是一种优化技术，主要用于通过存储昂贵的函数调用的结果来加速计算机程序，并在再次发生相同的输入时返回缓存的结果。

本文首先介绍一个简单的使用 memoization 优化技术的例子，然后解读 underscore 和 reselect 库中使用 memoization 的源码，加深理解。

阶乘 不使用 memoization

不假思索，我们会立即写下如下的代码：

const factorial = n => {
    if (n === 1) {
        return 1
    } else {
        return factorial(n - 1) * n
    }
};
使用 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
    }
};
使用 闭包 和 memoization

常见的方式是 闭包 和 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();

继续变形,下面这种编写方式是最常见的形式。

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

从阶乘的这个例子可以知道 memoization 是一个空间换时间的方式，存储执行结果，下次再次发生相同的输入会直接输出结果，提高了执行的速度。

underscore 源码中的 memoization 
// 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;
};

代码一目了然，使用 _.memoize 来实现阶乘如下：

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

参照这个源码，上面的阶乘继续可以变形如下：

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

从源码可以知道当 lastArgs 与 arguments 相同的时候，就不会再执行 func。

总结

memoization 是一种优化技术，避免一些不必要的重复计算，可以提高计算速度。

参考

Memoization wiki

Understanding JavaScript Memoization In 3 Minutes

Underscore

reselect

Implementing Memoization in JavaScript

GPU云服务器 云服务器 高级显示技巧 JAVASCRIPT技巧 javascript七大技巧 javascript调试技巧

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/98395.html

相关文章

  • Memoization in JavaScript

    摘要：源码函数调用过，没有变化，参数时返回缓存值。而通过，可以把上一次的计算结果保存下来，而避免重复计算。这意味着将跳过渲染组件，并重用最后渲染的结果。 1. 基本概念 在一个CPU密集型应用中，我们可以使用Memoization来进行优化，其主要用于通过存储昂贵的函数调用的结果来加速程序，并在再次发生相同的输入时返回缓存的结果。例如一个简单的求平方根的函数： const sqrt = Ma...

    ccj659 评论0 收藏0

  • 斐波那契数列求和的js方案以及优化

    摘要：在上做了一道斐波那契数列求和的题目，做完之后做了一些简单的优化和用另一种方法实现。动态规划解决方案斐波那契数列求和除了可以用递归的方法解决，还可以用动态规划的方法解决。 在codewars上做了一道斐波那契数列求和的题目，做完之后做了一些简单的优化和用另一种方法实现。 题目 function fibonacci(n) { if(n==0 || n == 1) r...

    xinhaip 评论0 收藏0

  • Python 应用剖析工具介绍

    摘要：免责声明不要过早地进行优化有关过早优化的详细分析请查阅本文。如果在庞大的应用中运行该分析工具，会得到一张巨大的图片。免责声明请确保该方法只用于函数如果将记忆用于带有副作用譬如的函数，缓存可能无法达到预期的效果。 【编者按】本文作者为来自 HumanGeo 的工程师 Davis，主要介绍了用于 Python 应用性能分析的几个工具。由国内 ITOM 管理平台 OneAPM 编译呈现。 在...

    lanffy 评论0 收藏0

  • JS专题之memoization

    摘要：前言在计算机领域，记忆是主要用于加速程序计算的一种优化技术，它使得函数避免重复演算之前已被处理过的输入，而返回已缓存的结果。被执行了不是素数，其他数字默认是素数。我们可以看出，如果从开始打印斐波那契数列，函数被执行了次。 前言 在计算机领域，记忆（memoization）是主要用于加速程序计算的一种优化技术，它使得函数避免重复演算之前已被处理过的输入，而返回已缓存的结果。 -- wi...

    zhisheng 评论0 收藏0

  • 【译】你可能不需要派生状态

    摘要：所有派生状态导致的问题无异于两种无条件的根据来更新无论和是否匹配来更新。派生状态最常见的错误就是将这两者混和在一起。因此通常被用于性能优化而不是来判断派生状态的正确性。我们可以使用派生状态来存储过滤列表这种方式避免了重新计算。 原文链接：https://reactjs.org/blog/2018... 翻译这篇文章的起因是因为在一次需求迭代中错误的使用了getDerivedState...

    dinfer 评论0 收藏0

发表评论

登陆后可评论

0条评论

刘德刚

男|高级讲师
我要私信

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<