js-语言精粹-函数记忆

函数可以将先前操作的结果记录在某个对象里，从而避免无谓的重复运算。这种优化方式被称为记忆（memoization）。JavaScript的对象和数组要实现这种优化是非常方便的。

比如说，我们想要一个递归函数来计算Fibonacci数列。一个Fib数字是之前两个Fib数字的和。最前面的两个数字是0和1。

var count=0;

var fib=function(n){

    count++;

    return n<2?n:fib(n-1)+fib(n-2);

};

for(var i=0;i<=10;i++){

    console.log(fib(i))

}

//

//

//

//

//

//

//

//

//

//

//

count

//

这样是可以工作的，但它做了很多无谓的工作，fib函数被调用了453次。如果我们让该函数具备记忆功能，就可以显著地减少运算量。

我们在一个名为memo的数组里保存我们的存储结果，存储结果可以隐藏在闭包中。当函数被调用时，这个函数首先检查结果是否已经存在，如果已经存在，就立刻返回这个结果。

var count=0;

var fibonacci=function(){

    var memo=[0,1];

    var fib=function(n){

                count++;

        var result=memo[n];

        if(typeof result!=='number'){

            result=fib(n-1)+fib(n-2);

            memo[n]=result;

        }

        return result;

    };

    return fib;

}();

for(var i=0;i<=10;i++){

    console.log(fibonacci(i))

}

//结果同上

count

//

这个函数返回同样的结果，但它只被调用了29次。

我们可以把这种技术推而广之，编写一个函数来帮助我们构造带记忆功能的函数。memoizer函数取得一个初始的memo数组和formula函数。它返回一个管理memo存储和在需要时调用formula函数的recur函数。我们把这个recur函数和它的参数传递给formula函数：

var memoizer=function(memo,formula){

    var recur=function(n){

        var result=memo[n];

        if(typeof result!=='number'){

            result=formula(recur,n);

            memo[n]=result;

        }

        return result;

    };

    return recur;

};

现在我们可以使用memoizer函数来定义fibonacci函数，提供其初始的memo数组和formula函数：

var fibonacci=memoizer([0,1],function(recur,n){

    return recur(n-1)+recur(n-2);

});

通过设计这种产生另一个函数的函数，极大的减少了我们的工作量。例如，要产生一个可记忆的阶乘函数，我们只需提供基本的阶乘公式即可：

var factorial=memoizer([1,1],function(recur,n){

    return n*recur(n-1);

});

巴特西

js-语言精粹-函数记忆

最新文章

热门文章