JavaScript专题之函数记忆

[mqyqingfeng]

定义

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

举个例子：

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]

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

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

[mqyqingfeng]

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

[HowardTangHw]

第一版中,

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

这里名字不一致,笔误了

[mqyqingfeng]

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

[vanishcode]

您好，请问这个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]

@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]

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

[mqyqingfeng]

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

[yoyoyohamapi]

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

[HuangQiii]

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

最大公约数（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]

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

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

[Gloomysunday28]

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

[forever-z-133]

方案一不使用 [].join 而是 JSON.stringify(arguments) 就能解决入参是对象的问题了吧

[gogoLJY]

第二版描述，"就会自动调用 toString 方法转换成 [Object object]"，应该是 [object Object]吧

[SaebaRyoo]

个人认为这个函数记忆就是设计模式中的代理模式，在函数中增加了缓存代理。

如果项目中有图表需要展示历史数据时，这会是一个很好的使用场景。正常的写法就是选择一个日期，然后发送一个http请求。但是在历史数据这种场景中，其实没必要去不停的请求服务器。下面是我写的一个简单的例子，大家可以看看。如有不对，务必指出。谢谢！

const getData = (() => {
  // 缓存
  const cache = new Map();
  return async function(date) {
      if (cache.has(date)) {
          return new Pormise((resolve) => {
              resolve(cache.get(date))
          })
      }
      return request('POST', '/list/history', { date })
      .then(data => {
          // 设置缓存
          cache.set(date, data);
          return data;
      })
  }
})()
const data = await getData('2019-12-31');

[bishinianshao]

大佬你好，前端小菜鸡想问下为啥第二版内部的memoize函数里参数key就是add函数的第一个参数呢

[KeithChou]

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

这里与工厂模式还不一样 工厂模式主要处理类 也就是处理多个类（简单工厂）或者多个工厂（复杂工厂）的过程

这里更像是代理模式 函数记忆也就是代理模式中的缓存代理

[JiaJiaJiayi]

大佬你好，前端小菜鸡想问下为啥第二版内部的memoize函数里参数key就是add函数的第一个参数呢

你好 因为我们平时写的function fn(a,b,c){...}中a是第一个参数，自然function fn(key){...}中key是第一个参数啦

[tb1565647408]

前面的专题还能吸收点，后面看着太跳级了，还是买两本书啃完再来了。

[lonfger]

@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

看这一段的时候没有想到~~哈哈哈哈哈，本以为去掉前面的length拼接问题也不大。。。。。学习到了

[lonfger]

大佬你好，前端小菜鸡想问下为啥第二版内部的memoize函数里参数key就是add函数的第一个参数呢

var memoizedAdd = memoize(add) 这一句其实就是返回memoize的函数重写，即：

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

所以在调用memoizedAdd(1,2,3)的时候key值就为1.

[fwqaaq]

使用ts改写了一下

• 这里默认是用fn作为,当然hasher就可以写为可选的类型

const memoize = function (fn: Function, hasher?: Function) {
  let cache: any ={}
  const menoize = function (...args: any[]) {
    const address = "" + (hasher ? hasher.apply(null, args) : args)
    if (!cache[address]) {
      cache[address] = fn.apply(null, args)
    }
    return cache[address]
  }
  return menoize
}

let add = function (a: number, b: number, c: number) {
  return a + b + c
}

let memoizedAdd = memoize(add)
console.log(memoizedAdd(1, 2, 3))