在JavaScript中用高阶函数与闭包实现函数的记忆功能

作者:admin     字体:[增加 减小]    类型:原创
在JavaScript中,函数的记忆只是一种编程技巧,本质上是牺牲算法的空间复杂度以换取更优的时间复杂度,并且以求最大公约数与求递归两个实列,来说明如何实现函数的记忆功能。

在函数式编程中,将缓存技巧叫做“记忆。需要注意的是,记忆只是一种编程技巧,本质上是牺牲算法的空间复杂度以换取更优的时间复杂度,在客户端JavaScript中代码的执行时间复杂度往往成为瓶颈,因此在大多数场景下,这种牺牲空间换取时间的做法以提升程序执行效率的做法是非常可取的。

下面的代码展示了一个高阶函数,memorize()接收一个函数作为实参,并返回带有记忆能力的函数。

//返回f()的带有记忆功能的版本
//只有当f()的实参的字符串表示都不相同时它才会作用
function memorize(f){
    var cache = {}; //将值保存在闭包内
    return function(){
        //将实参转换为字符串形式,将其用做缓存的键
        var key = arguments.length + Array.prototype.join.call(arguments,",");
        if(key in cache) return cache[key];
            else return cache[key] = f.apply(this,arguments);
    }
}

首先来看一个实例,这个实例是用记忆能功实现了求最大约数的函数

//返回两个整数的最大公约数
function gcd(a,b){  //这里省略对a和b的类型检查
    var t;          //临时变量用来存储交换数值
    if(a<b) t=b,b=a,a=t;    //确保a>=b
    while(b!=0) t=b,b=a%b,a=t;//这是求最大公约数的欧几里德算法
    return a;
}

var gcdmemo = memorize(gcd);
console.log(gcdmemo(85,187));   //17

从上面的代码中,我们可以看出memorize()函数创建一个新的对象,这个对象被当做缓存(的宿主)并赋值给一个局部变量,因此对于返回的函数来说它是私有的(在闭包中)。所返回的函数将它的参数数组转换成字符串,并将字符串用来缓存对象的属性名。如果在缓存中存在这个值,则直接返回它。

下面再看一个实例,它是用来求递归的

//注意,当我们写一个递归函数时,往往需要实现记忆功能
//我们更希望调用实现了记忆功能的递归函数,而不是原递归函数
var factorial = memorize(function(n){
    return (n<=1) ? 1 : n * factorial(n-1);
});

console.log(factorial(5));  //120,对于4~1的值也有缓存