JavaScript 使用函数实现“历史记录”

函数可以使用对象去记住先前操作的结果，从而避免多余的运算。

比如我们现在测试一个费波纳茨算法，我们可以使用递归函数计算fibonacci数列，一个fibonacci数字是之前两个fibonacci数字之和，最前面的两个数字是0和1。代码如下：

var count = 0;    //记录函数调用次数
 var fibonacci = function(n) {
    count++;
    return n < 2 ? n : fibonacci(n-1) + fibonacci(n-2);
 };
 for(var i = 0; i <= 10; i+=1) {
    console.log(i+":"+fibonacci(i));
 }
 console.log(count); // 453

我们可以看到如上 fibonacci函数总共调用了453次，for循环了11次，它自身调用了442次，如果我们使用下面的记忆函数的话，那么就可以减少他们的运算次数，从而提高性能。

思路：先使用一个临时数组保存存储结果，当函数被调用的时候，先查找是否已经有存储结果，如果有的话，就立即返回这个存储结果，没有的话，调用函数进行运算。代码如下：

var count2 = 0;
var fibonacci2 = (function(){
    var memo = [0,1];
    var fib = function(n) {
        var result = memo[n];
        count2++;
        if(typeof result !== 'number') {
            result = fib(n-1) + fib(n-2);
            memo[n] = result;
        }
        return result;
    };
    return fib;
 })();
 for(var j = 0; j <= 10; j+=1) {
    console.log(j+":"+fibonacci2(j));
 }
 console.log(count2); // 29

这个函数也返回了同样的结果，但是只调用了函数29次，循环了11次，也就是说函数自身调用了18次，从而减少无谓的函数的调用及运算，下面我们可以把这个函数进行抽象化，以构造带记忆功能的函数，如下代码：

var count3 = 0;
var memoizer = function(memo,formula) {
    var recur = function(n) {
        var result = memo[n];
        count3++;   // 这句代码只是说明运行函数多少次，在代码中并无作用，实际使用上可以删掉
        if(typeof result !== 'number') {
            result = formula(recur,n);
            memo[n] = result;
        }
        return result;
    };
    return recur;
 };
 var fibonacci3 = memoizer([0,1],function(recur,n){
    return recur(n-1) + recur(n-2);
 });
 // 调用方式如下
 for(var k = 0; k <=10; k+=1) {
    console.log(k+":"+fibonacci3(k));
 }
 console.log(count3); // 29

如上封装 memoizer 里面的参数是实现某个方法的计算公式，具体的可以根据需要自己手动更改，这里的思路无非就是想习惯使用对象去保存临时值，从而减少不必要的取值存储值的操作；

 

学习资源：理解使用函数实现历史记录--提高性能