与我联系

递归函数通过缓存提升性能

2017-8-20 一诺 js+jquery+ajax

递归应该是众所周知的概念,而且我们遇到次数最多的例子可能就是斐波那契数列了,规则如下:
f(n)=f(n-1)+f(n-2),                                                                             
    for n=2,3,4,...n and                                                                        
        f(0)=0 and f(1)=1                                                                     
一个斐波那契数列数列是前面两个斐波那契数的加和。
所以我们一般写的代码可能就是这样的:
function fibonacci(n) {                                                                         
    return n < 2 ? n : fibonacci(n - 1) + fibonacci(n - 2);                          
}                                                                                                       
这个算法以教学为目的,但非常低效的,不仅因为递归,而且两次调用fibonacci函数,在函数里面右侧调用的fibonacci(n-2) 在表达式左侧调用fibonacci(n-1)时就已完全计算过一遍。
对于这个特定卡塔(类似打怪升级里面的级数),我们想实现缓存的解决方案。这是特别酷的,因为它将让我们继续使用递归算法,同时仍然保持足够迅速的得到一个答案。
memoize的版本的诀窍是,保持一个缓存数据结构(最有可能的关联数组),将斐波纳契数列的值缓存。当获取一个斐波那契数列值时,首先在缓存中查找,如果有则直接返回值,如果没有,再计算并把它放进缓存。
使用memoize的数据结构重构函数的递归Fibonacci以避免递归调用的缺陷。
分析
斐波那契数列里面不断的递归调用自身,列入输入的是 70,那么需要计算69和68的值。
在计算69的过程中又计算了 68、67、、、、、1。 计算 68的过程又计算了 67、66、、、、、、、1的值,如此重复计算的值太多了,花费的时间也就比较多。
缓存思想恰好可以减少不必要的重复计算。当第一遍计算69的值时就递归计算了 68、67、66、、、1的值,之后的每次都先查看是否有缓存,有就直接返回缓存值,避免了重复计算。
代码
let cache = [];                                                                                       
let fibonacci = function(n) {                                                                    
    if(n < 2)                                                                                            
        return n;                                                                                        
    if(cache[n]){                                                                                      
      return cache[n];                                                                               
    }                                                                                                       
    return cache[n] = fibonacci(n-1) + fibonacci(n-2);                                  
}                                                                                                           

或者


var fibonacci = function() {                                                                       
    var memo = [0, 1];                                                                              
    var fib = function(n) {                                                                          
        var result = memo[n];                                                                      
        if (typeof result != "number") {                                                          
            result = fib(n - 1) + fib(n - 2);                                                       
            memo[n] = result;                                                                       
        }                                                                                                    
        return result;                                                                                   
    }                                                                                                        
    return fib;                                                                                           
}();                    


通过性能测试,当测试数是40时不适用缓存消耗的时间就是使用缓存的1700多倍(好可怕的数据)
Underscore.js库有提供实现该功能的memoize()函数。使用方法如下:
var fibonacci = _.memoize(function(n) {                                                    
  return n < 2 ? n: fibonacci(n - 1) + fibonacci(n - 2);                                 
}); 
对于耗时计算计算较长的计算,强烈推荐使用哦~

分享这篇文章
赞助鼓励:如果觉得内容对您有所帮助,您可以支付宝(左)或微信(右):

声明:如无特殊注明,所有博客文章版权皆属于作者,转载使用时请注明出处。谢谢!

发表评论:

皖ICP备15010162号-1 @2015 勿恨水长东
qq:1614245331 邮箱:13515678147@163.com Powered by
emlog