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

2017-8-20 Jon

递归应该是众所周知的概念，而且我们遇到次数最多的例子可能就是斐波那契数列了，规则如下：

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);                                 

});

对于耗时计算计算较长的计算，强烈推荐使用哦~

发表评论：