函数记忆

2018-08-12

摘要：冴羽的博客学习函数记忆

函数记忆

函数记忆是指将上次的计算结果缓存起来，当下次调用时，如果遇到相同的参数，就直接返回缓存中的数据。也就指明了函数记忆的使用场景：需要大量重复的计算，或者大量计算又依赖于之前的结果

第一版

// 《JavaScript权威指南》8.8.4记忆
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);
    }
  }
}

注意：使用join拼接参数字符串时要考虑到toString隐式转换，传入对象时会出现问题

第二版

// underscore
var memoize = function (func, hasher) { // hasher是参数处理函数
  var memoize = function (key) {
    var cache = memoize.cache;
    var address = '' + (hasher ? hasher.apply(this, arguments) : key); // hasher
    if (!cache[address]) { // 如果cache[address]存在，但是隐式转换后为false，比如0，那么仍会再次计算
      cache[address] = func.apply(this, arguments);
    }
    return cache[address];
  };
  memoize.cache = {};
  return memoize;
};

var fn = function(){
  // 执行程序
}

// 如果参数是对象，需要将对象序列化
var memoizedAdd = memoize(fn, function(){
  var args = Array.prototype.slice.call(arguments);
  return JSON.stringify(args);
})

以斐波那契数列（从第3项开始，每一项都等于前两项之和）为例：

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

每次计算索引大于1的值时都要先得到前两项的值，而前两项的索引如果大于1的话又需要得到更在前面的两项的值，这里面存在大量重复的计算

使用函数记忆

fibonacci = memoize(fibonacci)
for (var i = 0; i <= 10; i++) {
  fibonacci(i)
}
console.log(count) // 12