realazy在blog上给出了一个JavaScript Memoization的实现，Memoization就是函数返回值的缓存，比如一个函数参数与返回结果一一对应的hash列表，wiki上其实也有详细解释，我不细说了，只讨论一下具体实现的问题，realazy文中的代码有一些问题，比如直接用参数拼接成的字符串作为查询缓存结果的key，如果参数里包括对象或数组的话，就很难保证唯一的key，还有1楼评论里提到的：[221,3]和[22,13]这样的参数也无法区分。
那么来改写一下，首先还是用hash表来存放缓存数据：
- function Memoize(fn){
- var cache = {};
- return function(){
- var key = [];
- for( var i=0, l = arguments.length; i < l; i++ )
- key.push(arguments[i]);
- if( !(key in cache) )
- cache[key] = fn.apply(this, arguments);
- return cache[key];
- };
- }
嗯，区别是直接把数组当作键来用，不过要注意函数里的arguments是js解释器实现的一个特殊对象，并不是真正的数组，所以要转换一下……
ps: 原来的参数包括方法名称和上下文引用：fib.fib_memo = Memoize(‘fib_memo’, fib)，但实际上currying生成的函数里可以用this直接引用上层对象，更复杂的例子可以参考John Resig的makeClass，所以我改成直接传函数引用：fib.fib_memo = Memoize(fib.fib_memo)
这样写看上去似乎很靠谱，由参数组成的数组不是唯一的么。但实际上，数组之所以能作为js对象的属性名称来使用，是因为它被当作字符串处理了，也就是说如果你给函数传的参数是这样：(1,2,3), cache对象就会是这个样子：{ “1,2,3″: somedata }，如果你的参数里有对象，比如：(1,2,{i:”yy”})，实际的键值会是：”1,2,[object Object]“，所以这跟把数组拼接成字符串的方法其实没有区别……
示例：
- var a = [1,2,{yy:'0'}];
- var b = [1,2,{xx:'1'}];
- var obj = {};
- obj[a] = "111";
- obj[b] = "222";
- for( var i in obj )
- alert( i + " = " + obj[i] ); //只会弹出"1,2,[object Object] = 222"，obj[a] = "111"被覆盖了
直接用参数作为键名的方法不靠谱了…………换一种方法试试：
- function Memoize(fn){
- var cache = {}, args = [];
- return function(){
- for( var i=0, key = args.length; i < key; i++ ) {
- if( equal( args[i], arguments ) )
- return cache[i];
- }
- args[key] = arguments;
- cache[key] = fn.apply(this, arguments);
- return cache[key];
- };
- }
可以完全避免上述问题，没有使用hash的键值对索引，而是把函数的参数和结果分别缓存在两个列表里，每次都先遍历整个参数列表作比较，找出对应的键名/ID号之后再从结果列表里取数据。以下是比较数组的equal方法：
- function equal( first, second ){
- if( !first || !second || first.constructor != second.constructor )
- return false;
- if( first.length && typeof first != "string" )
- for(var i=0, l = ( first.length > second.length ) ? first.length : second.length; i<l; i++){
- if( !equal( first[i], second[i] ) ) return false;
- }
- else if( typeof first == 'object' )
- for(var n in first){
- if( !equal( first[n], second[n] ) ) return false;
- }
- else
- return ( first === second );
- return true;
- }
千万不要直接用==来比较arguments和args里的数组，那样比较的是内存引用，而不是参数的内容。
这种方法的速度很慢，equal方法其实影响不大，但是缓存的结果数量多了以后，每次都要遍历参数列表却是很没效率的（求80以上的fibonacci数列，在firefox3和safari3上都要40ms左右）
如果在实际应用中参数变动不多或者不接受参数的话，可以参考Oliver Steel的这篇《One-Line JavaScript Memoization》，用很短的函数式风格解决问题：
- function Memoize(o, p) {
- var f = o[p], mf, value;
- var s = function(v) {return o[p]=v||mf};
- ((mf = function() {
- (s(function(){return value})).reset = mf.reset;
- return value = f.apply(this,arguments); //此处修改过，允许接受参数
- }).reset = s)();
- }
示例：
- var fib = {
- temp: function(n){
- for(var i=0;i<10000;i++)
- n=n+2;
- return n;
- }
- }
- Memoize(fib,"temp"); //让fib.temp缓存返回值
- fib.temp(16); //执行结果：20006，被缓存
- fib.temp(20); //执行结果：20006
- fib.temp(10); //执行结果：20006
- fib.temp.reset(); //重置缓存
- fib.temp(10); //执行结果：20010
