奇妙的memoizer
Thu, 25 Dec 2008 11:26:06 +0800在Douglas Crockford的書《JavaScript: 優良部份》以及演講「Ajax Performance」中，看到memoizer這個奇妙的東西，利用他以及適當地調整遞迴函數，可以把遞迴函數改成用iteration的方式執行，當計算的參數較大時，效能改進很明顯。
memoizer的原理是，把每次計算的結果記錄下來，提供下次計算使用，這樣函數就不用每次都計算到遞迴結束，減少的冗餘計算很多，所以可以大幅改善效能，但是又能使用遞迴函數簡潔的好處。
下面這個例子依次用到memoizer, Y combinator以及遞迴函數原本的方式，做費氏數列的運算：
<html>
<script>
var memoizer = function (memo, fundamental) {
var shell = function (n) {
var result = memo[n];
if (typeof result !== 'number') {
result = fundamental(shell, n);
memo[n] = result;
}
return result;
};
return shell;
};
var Y = function(g) {
return (function(x) {
return g(function(n) {
return x(x)(n);
});
})(function(x) {
return g(function(n) {
return x(x)(n);
});
});
};
</script>
<body>
<script>
var count = 0;
var fab = memoizer([0,1], function(f,n){count++;return f(n-1)+f(n-2);});
alert(fab(10));
alert(count);
var count1 = 0;
var fab1 = Y(
function(f){
return function(n){
count1++;
if(n==0)
return 0;
if(n<3)
return 1;
return f(n-1) + f(n-2);
};
});
alert(fab1(10));
alert(count1);
var count2 = 0;
var fab2 = function(n) {
count2++;
if(n===0)
return 0;
if(n<3)
return 1;
return fab2(n-1) + fab2(n-2);
};
alert(fab2(10));
alert(count2);
</script>
</body>
</html>
從執行結果可以看出來，使用memoizer做了9次函數呼叫，同時使用Y combinator或是遞迴的狀況下呼叫了177次，效果非常可觀。Crockford在演講中舉的是fab(40)，如果靠遞迴要做331160280次呼叫，而使用memoizer只要做39次。
今天是耶誕節，Crockford在他的blog上邀請不同宗教的人一同歡度。所以應景地把這篇叫做「奇妙」的memoizer吧。