从斐波那契数列求值优化谈 _.memoize 方法

[lessfish]

斐波那契数列 应该都很熟悉，如何能够快速求得斐波那契数列中某项的值呢？

一个很显然的方法是正向地叠加求解：

"use strict";
const N = 1000;
let fibonacciNumber = [];

for (let i = 0; i < 1000; i++) {
  if (i < 2)
    fibonacciNumber[i] = i;
  else
    fibonacciNumber[i] = fibonacciNumber[i - 2] + fibonacciNumber[i - 1];
}

这样做有个「预处理」的过程，我们不知道需要预处理多大的数据，这就比较棘手，如果能给个数据范围，这无疑是最高效又简便的方法。

接着我们考虑每次独立求解（非严格模式下，函数内的 fibonacci 也能用 arguments.callee 来代替）：

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

很经典的递归，但是这样做出现了大量重复递归运算。我们可以缓存中间运算结果，大大提高效率，有点「记忆化」的意思：

"use strict";
let fibonacci = function() {
  // 缓存过程中计算结果
  let cache = {};
  return function(n) {
    // 没有被计算过
    if (!cache[n])
      cache[n] = n < 2 ? n : fibonacci(n - 2) + fibonacci(n - 1);

    return cache[n];
  }
}();

我们可以将 memoize 函数封装起来：

"use strict";
let memoize = function(func) {
  let cache = {};
  return function(key) {
    if (!cache[key])
      cache[key] = func.apply(this, arguments);
    return cache[key];
  }
}

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

与最开始的递归版相比，只是外面包了个 memoize 方法而已，使得整个 func 的计算能保存中间已经计算过的值。

最后我们来看看 underscore 对其的实现：

// Memoize an expensive function by storing its results.
//「记忆化」，存储中间运算结果，提高效率
// 参数 hasher 是个 function，用来计算 key
// 如果传入了 hasher，则用 hasher 来计算 key
// 否则用 key 参数直接当 key（即 memoize 方法传入的第一个参数）
// _.memoize(function, [hashFunction])
// 适用于需要大量重复求值的场景
// 比如递归求解菲波那切数
// @http://www.jameskrob.com/memoize.html
// create hash for storing "expensive" function outputs
// run expensive function
// check whether function has already been run with given arguments via hash lookup
// if false - run function, and store output in hash
// if true, return output stored in hash
_.memoize = function(func, hasher) {
  var memoize = function(key) {
    // 储存变量，方便使用
    var cache = memoize.cache;

    // 求 key
    // 如果传入了 hasher，则用 hasher 函数来计算 key
    // 否则用 参数 key（即 memoize 方法传入的第一个参数）当 key
    var address = '' + (hasher ? hasher.apply(this, arguments) : key);

    // 如果这个 key 还没被 hash 过（还没求过值）
    if (!_.has(cache, address))
      cache[address] = func.apply(this, arguments);

    // 返回
    return cache[address];
  };

  // cache 对象被当做 key-value 键值对缓存中间运算结果
  memoize.cache = {};

  // 返回一个函数（经典闭包）
  return memoize;
};

实现原理和 memoize 差不多，underscore 将缓存中间结果的 cache 对象绑在了闭包返回的函数上（当做函数的属性），同时增加了一个 hasher 函数选项，如果函数有好几个参数，那么我们可以传入这个 hasher 函数来计算 key 值，从而来 hash。

参考：关于 memoize 前后性能对比的可以看下这篇文章 Faster JavaScript Memoization For Improved Application Performance

[Cuilz]

看了楼主的分析收获很多，但是undersocre中的_.memorize()方法并不能对提升 fibonacci 方法本身的性能，_.memorize()提升的是多次调用情景下的性能：
var memo_fibonacci = _.memorize(fibonacci);
memo_fibonacci(30);
memo_fibonacci(30); // 这次的调用会使用上一次调用时的cache里存的值，才会有性能的提升；

而楼主帖子内自己写的memorize()应该是优化了fibonacci方法本身，和_.memorize()作用应该是不同的，希望楼主能清晰地说明这一点，容易引起误导，分析的如有不妥，希望能和楼主交流~

[bigggge]

@Cuilz 楼主的memorize()不也是缓存结果吗？貌似没对fibonacci方法优化，麻烦解释下

[JianShaw]

@bigggge
是缓存结果。

优化的话 ，下边的链接应该可以解决你的问题
https://segmentfault.com/a/1190000007115162

[fanyifanbumaimeng]

es6对尾递归进行了优化，现在也可以直接用尾递归来求解fib了。

[tingtingtinghuang]

更加确切的讲，_.memorize()是通过缓存来实现优化的，只要之后的运算用到了之前缓存下来的结果，那就是有优化了。
_.memorize()提升的是多次调用情景下的性能：
var memo_fibonacci = _.memorize(fibonacci);
memo_fibonacci(30);
memo_fibonacci(n); //纠正一下，上一次的cache其实缓存了[0,30]的值，不单单是n=30的值。
所以n等于其他数值的情况下也有优化。

[lgy87]

@fanyifanbumaimeng
TCO 主要是解决 stackoverflow 的问题的，递归太深的话栈会溢出。
它和 memoize 函数解决的可不是一回事哟。

个人愚见哈。请随时修正我。