Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

JavaScript专题之函数记忆 #46

Open
mqyqingfeng opened this issue Sep 6, 2017 · 12 comments

Comments

@mqyqingfeng
Copy link
Owner

commented Sep 6, 2017

定义

函数记忆是指将上次的计算结果缓存起来,当下次调用时,如果遇到相同的参数,就直接返回缓存中的数据。

举个例子:

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

// 假设 memoize 可以实现函数记忆
var memoizedAdd = memoize(add);

memoizedAdd(1, 2) // 3
memoizedAdd(1, 2) // 相同的参数,第二次调用时,从缓存中取出数据,而非重新计算一次

原理

实现这样一个 memoize 函数很简单,原理上只用把参数和对应的结果数据存到一个对象中,调用时,判断参数对应的数据是否存在,存在就返回对应的结果数据。

第一版

我们来写一版:

// 第一版 (来自《JavaScript权威指南》)
function memoize(f) {
    var cache = {};
    return function(){
        var key = arguments.length + Array.prototype.join.call(arguments, ",");
        if (key in cache) {
            return cache[key]
        }
        else {
            return cache[key] = f.apply(this, arguments)
        }
    }
}

我们来测试一下:

var add = function(a, b, c) {
  return a + b + c
}

var memoizedAdd = memoize(add)

console.time('use memoize')
for(var i = 0; i < 100000; i++) {
    memoizedAdd(1, 2, 3)
}
console.timeEnd('use memoize')

console.time('not use memoize')
for(var i = 0; i < 100000; i++) {
    add(1, 2, 3)
}
console.timeEnd('not use memoize')

在 Chrome 中,使用 memoize 大约耗时 60ms,如果我们不使用函数记忆,大约耗时 1.3 ms 左右。

注意

什么,我们使用了看似高大上的函数记忆,结果却更加耗时,这个例子近乎有 60 倍呢!

所以,函数记忆也并不是万能的,你看这个简单的场景,其实并不适合用函数记忆。

需要注意的是,函数记忆只是一种编程技巧,本质上是牺牲算法的空间复杂度以换取更优的时间复杂度,在客户端 JavaScript 中代码的执行时间复杂度往往成为瓶颈,因此在大多数场景下,这种牺牲空间换取时间的做法以提升程序执行效率的做法是非常可取的。

第二版

因为第一版使用了 join 方法,我们很容易想到当参数是对象的时候,就会自动调用 toString 方法转换成 [Object object],再拼接字符串作为 key 值。我们写个 demo 验证一下这个问题:

var propValue = function(obj){
    return obj.value
}

var memoizedAdd = memoize(propValue)

console.log(memoizedAdd({value: 1})) // 1
console.log(memoizedAdd({value: 2})) // 1

两者都返回了 1,显然是有问题的,所以我们看看 underscore 的 memoize 函数是如何实现的:

// 第二版 (来自 underscore 的实现)
var memoize = function(func, hasher) {
    var memoize = function(key) {
        var cache = memoize.cache;
        var address = '' + (hasher ? hasher.apply(this, arguments) : key);
        if (!cache[address]) {
            cache[address] = func.apply(this, arguments);
        }
        return cache[address];
    };
    memoize.cache = {};
    return memoize;
};

从这个实现可以看出,underscore 默认使用 function 的第一个参数作为 key,所以如果直接使用

var add = function(a, b, c) {
  return a + b + c
}

var memoizedAdd = memoize(add)

memoizedAdd(1, 2, 3) // 6
memoizedAdd(1, 2, 4) // 6

肯定是有问题的,如果要支持多参数,我们就需要传入 hasher 函数,自定义存储的 key 值。所以我们考虑使用 JSON.stringify:

var memoizedAdd = memoize(add, function(){
    var args = Array.prototype.slice.call(arguments)
    return JSON.stringify(args)
})

console.log(memoizedAdd(1, 2, 3)) // 6
console.log(memoizedAdd(1, 2, 4)) // 7

如果使用 JSON.stringify,参数是对象的问题也可以得到解决,因为存储的是对象序列化后的字符串。

适用场景

我们以斐波那契数列为例:

var count = 0;
var fibonacci = function(n){
    count++;
    return n < 2? n : fibonacci(n-1) + fibonacci(n-2);
};
for (var i = 0; i <= 10; i++){
    fibonacci(i)
}

console.log(count) // 453

我们会发现最后的 count 数为 453,也就是说 fibonacci 函数被调用了 453 次!也许你会想,我只是循环到了 10,为什么就被调用了这么多次,所以我们来具体分析下:

当执行 fib(0) 时,调用 1 次

当执行 fib(1) 时,调用 1 次

当执行 fib(2) 时,相当于 fib(1) + fib(0) 加上 fib(2) 本身这一次,共 1 + 1 + 1 = 3 次

当执行 fib(3) 时,相当于 fib(2) + fib(1) 加上 fib(3) 本身这一次,共 3 + 1 + 1 = 5 次

当执行 fib(4) 时,相当于 fib(3) + fib(2) 加上 fib(4) 本身这一次,共 5 + 3 + 1 = 9 次

当执行 fib(5) 时,相当于 fib(4) + fib(3) 加上 fib(5) 本身这一次,共 9 + 5 + 1 = 15 次

当执行 fib(6) 时,相当于 fib(5) + fib(4) 加上 fib(6) 本身这一次,共 15 + 9 + 1 = 25 次

当执行 fib(7) 时,相当于 fib(6) + fib(5) 加上 fib(7) 本身这一次,共 25 + 15 + 1 = 41 次

当执行 fib(8) 时,相当于 fib(7) + fib(6) 加上 fib(8) 本身这一次,共 41 + 25 + 1 = 67 次

当执行 fib(9) 时,相当于 fib(8) + fib(7) 加上 fib(9) 本身这一次,共 67 + 41 + 1 = 109 次

当执行 fib(10) 时,相当于 fib(9) + fib(8) 加上 fib(10) 本身这一次,共 109 + 67 + 1 = 177

所以执行的总次数为:177 + 109 + 67 + 41 + 25 + 15 + 9 + 5 + 3 + 1 + 1 = 453 次!

如果我们使用函数记忆呢?

var count = 0;
var fibonacci = function(n) {
    count++;
    return n < 2 ? n : fibonacci(n - 1) + fibonacci(n - 2);
};

fibonacci = memoize(fibonacci)

for (var i = 0; i <= 10; i++) {
    fibonacci(i)
}

console.log(count) // 12

我们会发现最后的总次数为 12 次,因为使用了函数记忆,调用次数从 453 次降低为了 12 次!

兴奋的同时不要忘记思考:为什么会是 12 次呢?

从 0 到 10 的结果各储存一遍,应该是 11 次呐?咦,那多出来的一次是从哪里来的?

所以我们还需要认真看下我们的写法,在我们的写法中,其实我们用生成的 fibonacci 函数覆盖了原本了 fibonacci 函数,当我们执行 fibonacci(0) 时,执行一次函数,cache 为 {0: 0},但是当我们执行 fibonacci(2) 的时候,执行 fibonacci(1) + fibonacci(0),因为 fibonacci(0) 的值为 0,!cache[address] 的结果为 true,又会执行一次 fibonacci 函数。原来,多出来的那一次是在这里!

多说一句

也许你会觉得在日常开发中又用不到 fibonacci,这个例子感觉实用价值不高呐,其实,这个例子是用来表明一种使用的场景,也就是如果需要大量重复的计算,或者大量计算又依赖于之前的结果,便可以考虑使用函数记忆。而这种场景,当你遇到的时候,你就会知道的。

专题系列

JavaScript专题系列目录地址:https://github.com/mqyqingfeng/Blog

JavaScript专题系列预计写二十篇左右,主要研究日常开发中一些功能点的实现,比如防抖、节流、去重、类型判断、拷贝、最值、扁平、柯里、递归、乱序、排序等,特点是研(chao)究(xi) underscore 和 jQuery 的实现方式。

如果有错误或者不严谨的地方,请务必给予指正,十分感谢。如果喜欢或者有所启发,欢迎 star,对作者也是一种鼓励。

@BuptStEve

This comment has been minimized.

Copy link

commented Sep 6, 2017

第一版里用到了【语句的结果值】,看起来感觉不太好...

// 第一版 (来自《JavaScript权威指南》)
function memoize(f) {
    var cache = {};
    return function(){
        ...
        else return cache[key] = f.apply(this, arguments) // 赋值表达式的值
    }
}
@mqyqingfeng

This comment has been minimized.

Copy link
Owner Author

commented Sep 6, 2017

@BuptStEve 哈哈,那我修改一下~

@HowardTangHw

This comment has been minimized.

Copy link

commented Sep 28, 2017

第一版中,

function memoize(f) {}
var memoizedAdd = memorize(add)

这里名字不一致,笔误了

@mqyqingfeng

This comment has been minimized.

Copy link
Owner Author

commented Oct 11, 2017

@HowardTangHw 非常感谢指出哈,请一定要接受我迟到的感谢~

@vanishcode

This comment has been minimized.

Copy link

commented Oct 20, 2017

您好,请问这个var key = arguments.length + Array.prototype.join.call(arguments, ",");里的length是啥意思为啥要加到开头?
我console.log之后是

{ '0': 1, '1': 2, '2': 3 }
31,2,3

这样?
原谅我比较笨o(TωT)o ....

@mqyqingfeng

This comment has been minimized.

Copy link
Owner Author

commented Oct 23, 2017

@vanishcode 应该是担心 Array.prototype.join.call(arguments, ",") 会导致缓存的 key 值相同,比如在一些特殊情况下:

function add(a, b) {
    console.log(a + b);
}

var memoizedAdd = memoize(add);

memoizedAdd(1, 2); // 3
memoizedAdd('1,2') // 3
@zhangruinian

This comment has been minimized.

Copy link

commented Nov 20, 2017

单词拼写少了一个字母
memorize 少了r

@mqyqingfeng

This comment has been minimized.

Copy link
Owner Author

commented Nov 21, 2017

@zhangruinian 其实没有拼写错误,underscore 和 lodash 都是用的 memoize,memoization来源于memo,备忘录的意思,因为这个方法主要是记录一个值,以便以后可以搜索它。

@yoyoyohamapi

This comment has been minimized.

Copy link

commented Aug 18, 2018

为什么所有文章都没有【参考资料】一节

@HuangQiii

This comment has been minimized.

Copy link

commented Dec 5, 2018

补充几个适用场景,其实作者在多说一句中已经讲出了精髓,需要大量重复的计算,或者大量计算又依赖于之前的结果

最大公约数(GCD)

function gcd(a,b){
  var temp;
  if (a < b) temp=b, b=a, a=temp;  // if a < b,switch
  while(b != 0) temp=b, b = a%b, a=temp;
  return a;
}

阶乘(factorial)

function factorial(n) {
  return (n <= 1) ? 1 : n * factorial(n-1);
}

可能都是些偏向数学的解决。但是扩展了思路,在遇到动态规划的问题时,更难想到优化点,比如很典型的上楼梯一次可以一步或者两部,问上10级有多少种走法,其实就有那么一些fibonacci的味道在里面。

更值得一提的是,memoize并不是拼错了也不是直觉中的memorize,memo是备忘录的意思,比如大家记下自己遇到的bug,以备在今后遇到时能尽快查找,和memory的记忆的概念是不同的,而动态规划中比较常见的有个备忘录算法,和这里的memo有相似之处(个人之见)。

(另,我一直好奇表情是怎么发的哈哈哈哈

@divasatanica

This comment has been minimized.

Copy link

commented Apr 2, 2019

判断 typeof cache[address] === 'undefined' 可以避开结果为 0 时又重新计算一次的问题

当然也要根据返回值的类型来确认缓存判空的方式,以上只是针对返回值类型为 number 时的情况

@Gloomysunday28

This comment has been minimized.

Copy link

commented May 29, 2019

其实就是设计模式里的工厂模式, 判断创建的对象是否存在于存列表

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
9 participants
You can’t perform that action at this time.