JavaScript 高级技巧 Memoization

2018-10-16 admin

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 是一种优化技术,避免一些不必要的重复计算,可以提高计算速度。

参考

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

原文链接:https://segmentfault.com/a/1190000016703106

本站文章除注明转载外,均为本站原创或编译。欢迎任何形式的转载,但请务必注明出处。

转载请注明:文章转载自 JavaScript中文网 [https://www.javascriptcn.com]

本文地址:https://www.javascriptcn.com/read-42864.html

文章标题:JavaScript 高级技巧 Memoization

相关文章
javascript是什么意思
avaScript是Netscape开发的一个对象脚本语言,它使用在世界各地数以百万计的网页和服务器应用程序上。 网景的JavaScript是ecma - 262版的标准脚本语言,和公布的标准只有轻微的差异。 与广为流行的错误理解相反,Ja...
2015-11-12
21天学通javascript
简介: 本书是Javascript入门教程。Javascript是Web开发中应用最早、发展最成熟、用户最多的脚本语言。其语法简洁,代码可读性在众多脚本语言中最好,它在使用时不用考虑数据类型,是真正意义上的动态语言。本书总分为四篇,共21章...
2015-11-16
JavaScript的组成
一个完整的JavaScript由3个部分组成:核心(ECMAScript) 文档对象模型(DOM) 浏览器对象模型(BOM) ECMAScript 描述了该语言的语法和基本对象 ; DOM 描述了处理网页内容的方法和接口 ; BOM 描...
2015-11-12
JavaScript 事件流、事件处理程序及事件对象总结
JS与HTML之间的交互通过事件实现。事件就是文档或浏览器窗口中发生的一些特定的交互瞬间。可以使用监听器(或处理程序)来预定事件,以便事件发生时执行相应的代码。这种在传统软件工程中被称为观察员模式,支持页面的行为与页面的外观之间的松散耦合。...
2017-04-05
JavaScript变量的声明
声明变量 变量在脚本中的首次亮相是在其声明中。 在变量首次出现时将会在内存中设置它,因此您稍后可在脚本中引用它。 应在使用变量之前先声明变量。 可以使用 var 关键字实现此目的。 <span id=“mt9” class=“sent...
2015-11-12
7个提高效率的JavaScript调试工具
鐜板湪鐨凧avaScript浜嬪疄涓婂凡鐒舵垚涓轰簡娴佽�岀殑web璇�瑷€锛屽嵆浣垮畠骞朵笉瀹岀編銆傚緢澶氱▼搴忓憳涓嶅枩娆㈢敤JavaScript鍐欎唬鐮侊紝鏄�鍥犱负鍐欏埌鍚庢潵鎬讳細鍑虹幇鍚勭�嶈帿鍚嶅叾濡欑殑bug锛岃€屼笖鍦ㄥ紑...
2015-11-11
JavaScript短路原理精简代码
js中||和&&的特性帮我们精简了代码的同时,也带来了代码可读性的降低,虽然高效,但请灵活使用。 在js逻辑运算中,0、""、null、false、undefined、NaN都会判为false,其他都为t...
2015-11-12
7个让JavaScript变得更好的注意事项
随着浏览器性能提高,伴随着新的HTML5的编程接口的稳步采用,网页上的JavaScript的音量在逐渐增加。然而,一个写得不好的程序编码却拥有着打破整个网站,让用户为之沮丧和驱赶潜在客户的潜力。 开发人员必须使用所有供他们任意使用的工具和技...
2015-11-12
《JavaScript快速查询手册》PDF
下载地址:《JavaScript快速查询手册》PDF下载 http://pan.baidu.com/s/130rP8’ 简介: JavaScript快速查询手册 目录 前言 第一部分 命令查询 第二部分 JavaScript语句与运算符 第...
2015-11-16
javaScript+turn.js实现图书翻页效果实例代码
为了实现图书翻页的效果我们在网上可以看到很多教程 在这里推荐turn.js 网上的turn.js 有api 不过是英文的  很多人看起来不方便 .关于代码也是奇形怪状在这里我将详细讲解如何使用turn.js实现翻页效果 ,本篇文章只是讲解 ...
2017-03-16
回到顶部