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