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

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

Open
lessfish opened this issue Oct 14, 2016 · 6 comments
Open

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

lessfish opened this issue Oct 14, 2016 · 6 comments

Comments

@lessfish
Copy link
Owner

lessfish commented Oct 14, 2016

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

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

"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
Copy link

Cuilz commented Dec 19, 2016

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

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

@bigggge
Copy link

bigggge commented Feb 17, 2017

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

@JianShaw
Copy link

@bigggge
是缓存结果。

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

@fanyifanbumaimeng
Copy link

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

@tingtingtinghuang
Copy link

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

@lgy87
Copy link

lgy87 commented Apr 5, 2018

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

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

7 participants