javascript中的memoization(memoizing) 技术介绍

最近在读《JavaScript 设计模式》一书，其中工厂模式中提到了memoizing技术，今天仔细整理了一下memoization 相关的资料，与大家共享。

• Memoization的定义：

memoization 一词是Donald Michie 根据拉丁语memorandum杜撰的一个词。相应的动词、过去分词、ing形式有memoiz、memoized、memoizing.

Memoization 是一种将函数返回值缓存起来的方法，Memoization 原理非常简单，就是把函数的每次执行结果都放入一个键值对(数组也可以，视情况而定)中，在接下来的执行中，在键值对中查找是否已经有相应执行过的值，如果有，直接返回该值，没有才 真正执行函数体的求值部分。很明显，找值，尤其是在键值对中找值，比执行函数快多了。现代 JavaScript 的开发也已经大量使用这种技术。

•  一个简单的使用memoization的例子

我们知道，在不同的浏览器中，xmlHttpRequest对象的具体实现都不同。需要判断何种浏览器以执行具体的方法。这里就有一个使用memoization来实现的例子。

1. function createXHRObject = function(){
2.     //先把三个匿名函数缓存起来。
3.     var methods = [
4.         function(){return new XMLHttpRequest();},
5.         function(){return new ActiveXObject("Msxml2.XMLHTTP");},
6.         function(){return new ActiveXObject("Microsoft.XMLHTTP");}
7.     ];
8.     for(var i=0,len=methods.length;i<len;i++){
9.         try{//这里用try catch来代替了条件判断，通常我不赞成这种写法
10.             methods[i]();
11.         }
12.         catch(e){
13.             continue;//如果报异常，则执行下一次循环
14.         }
15.         // 把createXHRObject 与能正常执行的匿名函数对应起来，再调用createXHRObject不用再检测浏览器了
16.         createXHRObject = method[i];
17.         return method[i];
18.     }
19. }

以上是一个简单的例子，第一次执行createXHRObject（）的时候，会循环判断methods 中的方法，获取一个能正确执行的，并将createXHRObject的引用指向这个方法。以后再使用这个方法的时候，不用去判断，直接自动获取正确的方法。这省去了频繁的ajax调用中浏览器的检测。

当然，这个方法看上去效率的提升不是特别明显，我之所以写上来，是因为能比较清晰的理解memoization是如何实现的。在递归调用的时候，memoization的威力才能更好的显现。

一个递归的例子：

1. function fib(n) {
2. if (n < 2) {
3. return n;
4. }
5. return fib(n - 1) + fib(n - 2);
6. }

 这是一个经典的斐波纳契序列，fib(20) 会把fib这个方法执行21891次，如果是fib(40),这会执行331160281次。

再看看如何使用memoization来实现，由于fib的参数就是一个自然数，这里用一个数组来缓存fib函数执行的结果。数组的下标用来标识参数，该小标对应的值用来表示函数执行的结果。

1.  var iterMemoFib = (function() {
2.     var cache = [1, 1];
3.     var fib = function(n) {
4.         if (n >= cache.length) {
5.             //将一个递归转换成了一个遍历
6.             for (var i = cache.length; i <= n; i++) {
7.                 cache[i] = cache[i - 2] + cache[i - 1];
8.             }
9.         }
10.         return cache[n-1];
11.     }
12.     return fib;
13. })();

将Function的原型扩展memoize 和unmemoize 方法，这样你可以对任何函数实现memoize和解除memoize,当然，这个方法要慎重，对一些不是频繁执行的函数，没必要缓存：

1. Function.prototype.memoize = function() {
2.     var pad  = {};
3.     var self = this;
4.     var obj  = arguments.length > 0 ? arguments[i] : null;
5.  
6.     var memoizedFn = function() {
7.         // 把参数作为数组保存，作为键，把函数执行的结果作为值缓存起来
8.         var args = [];
9.         for (var i = 0; i < arguments.length; i++) {
10.             args[i] = arguments[i];
11.         }
12.         if (!(args in pad)) {
13.             pad[args] = self.apply(obj, arguments);
14.         }
15.         return pad[args];
16.     }
17.     memoizedFn.unmemoize = function() {
18.         return self;
19.     }
20.     return memoizedFn;
21. }
22. Function.prototype.unmemoize = function() {
23.     alert("Attempt to unmemoize an unmemoized function.");
24.     return null;
25. }
26.  

使用方法：

fib.memoize();

参考文档：

1. Memoizing functions in JavaScript
2. JavaScript Memoization
3. 提升JS性能：将递归转换为迭代
4. MemoizationFrom Wikipedia, the free encyclopedia

Copyright playgoogle.com© 2008

继续阅读《javascript中的memoization(memoizing) 技术介绍》的全文内容...

相关文章:

javascript链式调用的设计  (2009-7-29 22:19:31)

onbeforeunload与a标签在IE中的冲突  (2009-7-25 14:57:51)

基于jQuery UI的图片截取(圈人)功能  (2009-7-21 15:0:11)

整理：详解javascript function中的caller,callee,call,apply  (2009-7-4 11:41:33)

jQuery的不足之处  (2009-6-20 20:54:4)

---

最新评论:

• 2009-8-10 21:2:10，celi ： 很不错，有嚼头。