先看一段刻意磨磘 CPU 的程式:
var flower = function () {
var t = 0, i = 0;
for (; i < 5000000; i++) {
t++;
}
return t;
};
它每次被呼叫都要重跑一遍五百萬次的迴圈,假設耗時 2~3 秒。問題來了:如果同樣的輸入被反覆要求計算,我們真的要一直重算嗎?
Memoization(記憶化)是一種以空間換時間的策略:第一次呼叫時照常計算並把結果存起來,之後遇到相同參數就直接回傳快取值,不再進入運算流程。對於純函式(相同輸入必得相同輸出)效果最明顯。
var Memoize = function (fn, cache, refetch, obj) {
cache = cache || {}; // 用來存放計算結果
return function () {
// 多參數時以 '__' 串接成唯一 key,單參數直接用該參數
var k = arguments[1]
? Array.prototype.join.call(arguments, '__')
: arguments[0];
// 快取中沒有,或結果等於指定的 refetch 值時,重新計算
if (!(k in cache) || (refetch && cache[k] == refetch)) {
cache[k] = fn.apply(obj || fn, arguments); // obj 可改變 this 指向
}
return cache[k];
};
};
var fastFlower = Memoize(flower);
console.time('第一次');
fastFlower(); // 真的跑迴圈
console.timeEnd('第一次');
console.time('第二次');
fastFlower(); // 直接回傳快取
console.timeEnd('第二次');
第二次的耗時幾乎可以忽略不計。
這個模式很好用,但不是萬靈丹:
[object Object]。結論:Memoization 是把重複計算成本轉為一次性的空間成本,用在純粹、昂貴、重複呼叫頻繁的函式上,收益最直接。