JavaScript记忆函数

2015-03-28 71

最近在做关于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