JavaScript Memoization
Memoization 是一种将函数返回值缓存起来的方法，在 Lisp, Ruby, Perl, Python 等语言中使用非常广泛。随着 Ajax 的兴起，客户端对服务器的请求越来越密集（经典如 autocomplete），如果有一个良好的缓存机制，那么客户端 JavaScript 程序的效率的提升是显而易见的。
Memoization 原理非常简单，就是把函数的每次执行结果都放入一个散列表中，在接下来的执行中，在散列表中查找是否已经有相应执行过的值，如果有，直接返回该值，没有才真正执行函数体的求值部分。很明显，找值，尤其是在散列中找值，比执行函数快多了。现代 JavaScript 的开发也已经大量使用这种技术。
我通过 Google 寻找了好几种 JavaScript Memoization 的实现，都不太如人愿，有的实现不能缓存递归函数，有的需要修改函数的 prototype，于是自己实现一个：
/**
* JavaScript Momoization
* @param {string} func name of function / method
* @param {object} [obj] mothed's object or scope correction object
*
* MIT / BSD license
*/
function Memoize(func, obj){
var obj = obj || window,
func = obj[func],
cache = {};
return function(){
var key = Array.prototype.join.call(arguments, "");
var key = Array.prototype.join.call(arguments, "_")
if (!(key in cache))
cache[key] = func.apply(obj, arguments);
return cache[key];
}
}并写了一个测试案例，空口无凭，让大家亲自看看 Memoization 的威力。
见：http://realazy.org/lab/memoization.html
另，例子中的 fibonacci 函数有很多更有效率的实现方法，在此我使用最无效率的递归实现，只是为了更直达地演示 memoization.
又，longwosion 留言所提到的 key 唯一性问题，我略作修正，但应该还有更好的办法，欢迎您留言探讨。
April 23rd, 2008 at 02:21
多参数时，用那样的方式形成key的话不能保证唯一性。比如，我们要写一个下面的组合函数的话。
var comm = {
comm: function(m, n) {
if(n==0) return 1;
if(m==n) return 1;
if(n==1) return m;
return this.comm(m-1,n) + this.comm(m-1,n-1);
},
comm_memo: function(m, n) {
if(n==0) return 1;
if(m==n) return 1;
if(n==1) return m;
return this.comm_memo(m-1,n) + this.comm_memo(m-1,n-1);
}
}
comm.comm_memo = Memoize(‘comm_memo’, comm);
下面两组参数会获得一样的结果，显然是不对的。
[221,3]
[22,13]
April 23rd, 2008 at 09:01
求 fib(n)? 乱吵一下, 当个小总结.
1 应该使用尾递归, 只是加一个参数…
2 应该使用矩阵乘法, 可以在 O(logn) 的时间内…
or 用这个结论
fib(2n) = fib(n-1)*fib(n) + fib(n)*fib(n+1)
fib(2n+1) = fib(n)^2 + fib(n+1)^2
fib(2n-1) = fib(n-1)^2 + fib(n)^2
—
ps: 楼上这位的程序, 也有相当大的优化空间.
April 23rd, 2008 at 09:25
@longwosion – 你的建议不错。
另外，不递归的话不能够提升效率吧，如果cache能够成为obj的私有属性或许不递归也能提升效率。
April 23rd, 2008 at 09:47
>>随着 Ajax 的兴起，客户端对服务器的请求越来越密集（经典如 autocomplete），如果有一个良好的缓存机制，那么客户端 JavaScript 程序的效率的提升是显而易见的。
既然需求是解决服务器请求过多的问题，那么直接缓存 Ajax 请求(URL + get/post 的数据)的结果应该可以解决问题，直接缓存函数貌似太复杂了。
April 23rd, 2008 at 10:06
帅！ 前些日子还在想， 怎么能在前端做个很好的cache。 发现一些开源框架会缓存住selector取得的元素信息， 以为自己能做的只是尽可能缓存取来的数据。 这个利用闭包缓存住函数执行结果的方法提供了新的思路， 很赞：）
April 23rd, 2008 at 10:08
现在的前端开发对于程序的效率越来越高也越来越体系化了。。。
不错，学习中。。
April 23rd, 2008 at 14:37
@魏中华
或许我没说得太明白。我的意思是，在自动完成的输入过程中，在客户端缓存已经查找过的结果，在没有离开页面时，再次查找相同的值时，直接使用缓存结果了，并不用重新请求（即使请求已经缓存），而且也节省了函数的运行时间。
April 23rd, 2008 at 15:54
学习了。之前有关于“兼容性记忆体”的想法：就是浏览器在第一次执行某兼容代码时，记忆此时选择执行的分支，以确认当前浏览器支持的对象/方法，在以后的执行过程中，直接使用记忆体里的对象/方法。部分示例如下：
XmlHttpRequest.AXO = [
'MSXML3.XMLHTTP.5.0',
'MSXML3.XMLHTTP.4.0',
'MSXML3.XMLHTTP.3.0',
'MSXML3.XMLHTTP.2.0',
"Msxml3.XMLHTTP",
"Msxml2.XMLHTTP.5.0",
"Msxml2.XMLHTTP.4.0",
"Msxml2.XMLHTTP.3.0",
"Msxml2.XMLHTTP",
"Microsoft.XMLHTTP"];
XmlHttpRequest.AXOI=0; // 兼容性记忆体。
…
if(window.ActiveXObject){ // 支持ActiveX的（ie）
for (var i=XmlHttpRequest.AXOI, l=XmlHttpRequest.AXO.length; i
April 23rd, 2008 at 22:27
提个建议，要是Memoize函数能够接受 Refresh参数就更好了，
毕竟实际应用中有需要刷新cache 的需求。
btw，仰慕博主的威名，希望和博主有更多交流，方便请加我MSN：dylanjia@hotmail.com
期盼！
April 23rd, 2008 at 23:14
refresh希望渺茫。
另，参数唯一性：参数本身使用逗号分隔，何不将就。
var key = Array.prototype.join.call(arguments);
April 27th, 2008 at 04:16
不应该把参数拼成字符串作key，如果参数里有object或数组之类的就败了哑，不如改成这样：
function Memoize(fn){
var cache = {}, args = [];
return function(){
for( var i=0, key = args.length; i second.length ) ? first.length : second.length; i
April 27th, 2008 at 11:05
…评论有字数限制么…
我贴到BLOG上了：http://www.limboy.com/2008/04/27/javascript_memoization/
May 7th, 2008 at 09:46
函数中包含global对象 就不能用这个函数了
May 7th, 2008 at 10:02
你的文章回复系统 怎么设置的
我的回复http://hi.baidu.com/emkiao/blog/item/6612caedb8e0c3d1b21cb124.html
May 12th, 2008 at 17:20
这东西似乎只能用在一个函数上。绑两个以上的函数就冲突了，想法很好但还要再通用些吧。
July 18th, 2008 at 14:10
@闲耘
虽然join默认使用逗号分隔，但是作为key貌似不可以哦^-^
July 18th, 2008 at 15:29
晕，搞错了，作为对象的KEY可以的
April 3rd, 2009 at 23:12
我根据你的也做了个
var Every = function(array, callback, thisObject){
if(array.every){
return array.every(callback, thisObject);
}else{
for (var i = 0, len = array.length; i < len; i++) {
if(!callback.call(thisObject, array[i], i, array)) return false;
}
return true;
}
}
function Memoize(func, object){
var caches = [];
return function(){
var args = Array.prototype.slice.call(arguments), len = args.length;
for (var i = 0, n = caches.length; i < n; i++) {
var argC = caches[i]["args"];
if( argC.length == len && Every(argC, function(x, i){ return x === args[i]; })) return caches[i]["result"];
}
var result = func.apply(object, arguments);
caches.push({“args”: args, “result”: result});
return result;
}
}
function fib(n){
if (n == 0 || n == 1)
return 1;
return fib(n-1) + fib(n-2);
}
fib = Memoize(fib);
June 10th, 2009 at 23:02
在Ajaxian.com上看到的一个:
http://ajaxian.com/index.php?s=Memoization+&searchbutton=go
// memoize: a general-purpose function to enable a function to use memoization
// func: the function to be memoized
// context: the context for the memoized function to execute within
// Note: the function must use explicit, string-serializable parameters
function memoize (func, context) {
function memoizeArg (argPos) {
var cache = {};
return function () {
if (argPos == 0) {
if (!(arguments[argPos] in cache)) {
cache[arguments[argPos]] = func.apply(context, arguments);
}
return cache[arguments[argPos]];
}
else {
if (!(arguments[argPos] in cache)) {
cache[arguments[argPos]] = memoizeArg(argPos – 1);
}
return cache[arguments[argPos]].apply(this, arguments);
}
}
}
// JScript doesn’t grok the arity property, but uses length instead
var arity = func.arity || func.length;
return memoizeArg(arity – 1);
}
November 25th, 2009 at 10:38
[...] JavaScript Memoization [...]