JavaScript记忆函数

最近在做关于JS图像处理的事情,性能瓶颈遇到很多。今天上课舍友突然告诉我说找到一个方法可能能对性能进行优化。这个东西就是记忆函数,说的挺高端,其实就是闭包的原理

无记忆斐波那契函数

直接上代码:

/**
 * 无记忆斐波那契函数
 */
function fabonacci_noMemory(x) {
    if (x < 2) {
        return 1;
    }
    return fabonacci_noMemory(x - 1) + fabonacci_noMemory(x - 2);
}

var startTime = +new Date();

var noMemoryResult = fabonacci_noMemory(40);

var endTime = +new Date();

console.log("no memory result : " + noMemoryResult);
console.log("no memory time : " + (endTime - startTime));

上面的代码是没有应用记忆函数的时候,非常之简洁,写出来简直佩服造物主的伟大。
但是...这个时候显然用递归的时候每次需要重新计算,那么这个时间复杂度是多少呢?


可以看出来,如果计算F(n)的话,要进行F(n-2)次计算!这尼玛是指数级的复杂度啊,少年你这么玩计算机,计算机可受不了啊!
那么我们要怎么搞?很显然发现有很多计算都是重复的,不必要的,那我们就可以把计算过的值存下来,在接下来的计算中直接拿去用就好了,当然这个假设是基于有足够的内存让你储存之前计算过的值。

闭包简单回顾

那么怎么在JavaScript中存储这些先前计算过的值呢?我们先回顾一个闭包的例子:

/**
 * 闭包例子
 * @returns {{getCount: Function, incCount: Function}}
 * @constructor
 */
function Count(){
    var count = 0;

    return {
        getCount : function () {
            return count;
        },

        incCount : function () {
            count ++;
        }
    }
}

var countInstance = new Count();

相信之前我们了解过闭包了,在这个例子中,countInstance活动对象中的count就相当于一个独立存储的变量。这里的细节我就不说了,不了解的同学可以参考这篇文章

记忆斐波那契函数

那么同理,我们同样用闭包来实现记忆函数。
方法如下:

/**
 * 记忆斐波那契构造函数
 */
function Fabonacci_memory() {
    var cache = {};

    return {
        fabonacci : function (x) {
            if (x < 2) {
                return 1;
            } else {
                if (!cache[x]) {
                    cache[x] = this.fabonacci(x - 1) + this.fabonacci(x - 2);
                }
                return cache[x];
            }
        }
    }
}


var fabonacci_memory_instance = new Fabonacci_memory();

var memoryStart = +new Date();

var result = fabonacci_memory_instance.fabonacci(40);

var memoryEnd = +new Date();

console.log("memory result : " + result);
console.log("memory time : " + (memoryEnd - memoryStart));

在这个cache对象中,就存有之前计算过的值,这样在之后的运算中如果遇到了前面已经运算过的值,就可以直接在cache中取出来即可。这样的复杂度就将到O(n)了,这才是一个程序员应做的事情。

结果如下:

这里我用的40作为参数计算,可以发现记忆函数一下子就完了,但是无记忆的用掉了1456ms,在我的试验中,大概结果:

参数 无记忆函数所用时间(s) 记忆函数所用时间(ms)
40 1.456 0
45 15 0
50 懒得等 0
1000 懒得等 0
10000 世界末日 3

### 遗留问题 @TODO
但是,其实很多时候我们不推荐使用闭包,特别是这种大容量的闭包,因为用完之后一直保持着对其的引用,导致GC无法回收,容易造成内存泄露。但是我用chrome调试内存调了一晚上也没有发现端倪,

参考资料

http://www.guokr.com/blog/68001/
http://blog.csdn.net/junjun16818/article/details/8542068