缓存

引子

fibonacci 数列相信大家不会陌生:

在 JavaScript 中,我们对其递归求解:

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

fibonacci(5); // => 5

我们仔细看一下 fibonacci(5) 的递归过程:

fibonacci(5)
fibonacci(5) = fibonacci(4)+fibonacci(3)
fibonacci(4) = fibonacci(3)+fibonacci(2)
fibonacci(3) = fibonacci(2)+fibonacci(1)
// ....

可以看到,在该递归过程中,引起了很多的重复计算,所以我们考虑将计算结果进行缓存。为此,我们需要利用到高阶函数闭包

var fibonacciWithMemo = (function() {
  var memo = {};
  return function fibonacci(n) {
    // 如果尚未建立缓存
    if(!memo[n]) {
      memo[n] = n < 2 ? n : fibonacci(n-1) + fibonacci(n-2);
    }
    return memo[n];
  }
}());

测试

console.time("没有缓存优化的fibonacci");
fibonacci(40);
console.timeEnd("没有缓存优化的fibonacci");
// => "没有缓存优化的fibonacci: 1505.980ms"

console.time("使用缓存优化的fibonacci");
fibonacciWithMemo(40);
console.timeEnd("使用缓存优化的fibonacci");
// => "使用缓存优化的fibonacci: 0.281ms"

上面我们的缓存工厂函数还只能创建一个带缓存记忆的 fibonacci 计算函数,underscore 则为我们封装了一个通用的缓存函数创建器 -- _.memoize

_.memoize

_.memoize(func, hasher):为函数 func 提供记忆功能,hasher 定义如何获得缓存。

_.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 将缓存绑定到了缓存函数的 cache 属性上,在创建一个缓存函数时,除了提供原函数 func 用来计算值外,还可以提供 hasher 函数来自定义如何获得缓存的位置。如果 hasher 不设置,则以缓存函数的参数 key 标识缓存位置。

用例

  • 不传递hasher
var fibonacci = _.memoize(function(n) {
    return n < 2 ? n: fibonacci(n-1) + fibonacci(n-2);
});

fibonacci(5); // => 5
console.log(fibonacci.cache);
// {
//   0: 0,
//   1: 1,
//   2: 2,
//   3: 2,
//   4: 3,
//   5: 5
// }
  • 传递hasher
var hasher = function() {
    var n = arguments[0];
    return n;
}

var fibonacci = _.memoize(function(n) {
    return n < 2 ? n: fibonacci(n-1) + fibonacci(n-2);
}, hasher);

fibonacci(5); // => 5
console.log(fibonacci.cache);
// {
//   0: 0,
//   1: 1,
//   2: 2,
//   3: 2,
//   4: 3,
//   5: 5
// }

results matching ""

    No results matching ""