Open lessfish opened 7 years ago
看了楼主的分析收获很多,但是undersocre中的.memorize()方法并不能对提升 fibonacci 方法本身的性能,.memorize()提升的是多次调用情景下的性能: var memofibonacci = .memorize(fibonacci); memo_fibonacci(30); memo_fibonacci(30); // 这次的调用会使用上一次调用时的cache里存的值,才会有性能的提升;
而楼主帖子内自己写的memorize()应该是优化了fibonacci方法本身,和_.memorize()作用应该是不同的,希望楼主能清晰地说明这一点,容易引起误导,分析的如有不妥,希望能和楼主交流~
@Cuilz 楼主的memorize()不也是缓存结果吗?貌似没对fibonacci方法优化,麻烦解释下
@bigggge
是缓存结果。
优化的话 ,下边的链接应该可以解决你的问题 https://segmentfault.com/a/1190000007115162
es6对尾递归进行了优化,现在也可以直接用尾递归来求解fib了。
更加确切的讲,.memorize()是通过缓存来实现优化的,只要之后的运算用到了之前缓存下来的结果,那就是有优化了。 .memorize()提升的是多次调用情景下的性能: var memofibonacci = .memorize(fibonacci); memo_fibonacci(30); memo_fibonacci(n); //纠正一下,上一次的cache其实缓存了[0,30]的值,不单单是n=30的值。 所以n等于其他数值的情况下也有优化。
@fanyifanbumaimeng TCO 主要是解决 stackoverflow 的问题的,递归太深的话栈会溢出。 它和 memoize 函数解决的可不是一回事哟。
个人愚见哈。请随时修正我。
斐波那契数列 应该都很熟悉,如何能够快速求得斐波那契数列中某项的值呢?
一个很显然的方法是正向地叠加求解:
这样做有个「预处理」的过程,我们不知道需要预处理多大的数据,这就比较棘手,如果能给个数据范围,这无疑是最高效又简便的方法。
接着我们考虑每次独立求解(非严格模式下,函数内的 fibonacci 也能用 arguments.callee 来代替):
很经典的递归,但是这样做出现了大量重复递归运算。我们可以缓存中间运算结果,大大提高效率,有点「记忆化」的意思:
我们可以将 memoize 函数封装起来:
与最开始的递归版相比,只是外面包了个 memoize 方法而已,使得整个 func 的计算能保存中间已经计算过的值。
最后我们来看看 underscore 对其的实现:
实现原理和 memoize 差不多,underscore 将缓存中间结果的 cache 对象绑在了闭包返回的函数上(当做函数的属性),同时增加了一个 hasher 函数选项,如果函数有好几个参数,那么我们可以传入这个 hasher 函数来计算 key 值,从而来 hash。
参考:关于 memoize 前后性能对比的可以看下这篇文章 Faster JavaScript Memoization For Improved Application Performance