JavaScript Memoization 让函数也有记忆功能

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了JavaScript Memoization 让函数也有记忆功能，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4768字，纯文字阅读大概需要7分钟。

内容图文

var fibonacci = function (n) { 
return n < 2 ? n : fibonacci(n - 1) + fibonacci(n - 2); 
}; 

for (var i = 0; i <= 10; i += 1) { 
document.writeln('// ' + i + ': ' + fibonacci(i)); 
} 

// 0: 0 
// 1: 1 
// 2: 1 
// 3: 2 
// 4: 3 
// 5: 5 
// 6: 8 
// 7: 13 
// 8: 21 
// 9: 34 
// 10: 55 
 
这样是可以工作的，但是它做了很多无谓的工作。 Fibonacci 函数被调用了 453 次。我们调用了 11 次，而它自身调用了 442 次去计算可能已经被刚计算过的值。如果我们让该函数具备记忆功能，就可以显著地减少它的运算量。 

我们在一个名为 memo 的数组里保存我们的储存结果，储存结果可以隐藏在闭包中。当我们的函数被调用时，这个函数首先看是否已经知道计算的结果，如果已经知道，就立即返回这个储存结果。 
 代码如下:

var fibonacci = function() { 
var memo = [0, 1]; 
var fib = function (n) { 
var result = memo[n]; 
if (typeof result !== 'number') { 
result = fib(n - 1) + fib(n - 2); 
memo[n] = result; 
} 
return result; 
}; 
return fib; 
}(); 
 
这个函数返回同样的结果，但是它只被调用了 29 次。我们调用了它 11 次，它自身调用了 18 次去取得之前储存的结果。 
以上内容来自:http://demon.tw/programming/javascript-memoization.html

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 
 






            
            


           
                
                                                

内容总结

以上是互联网集市为您收集整理的JavaScript Memoization 让函数也有记忆功能全部内容，希望文章能够帮你解决JavaScript Memoization 让函数也有记忆功能所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端