近來閱讀《JavaScript 設計模式》一書時,注意到工廠模式中提到了 memoizing 技術。這個看似不起眼的概念,卻能在特定場景下大幅提升程式效能。本文將系統梳理 memoization 的原理與實作,並透過兩個經典範例帶你領略它的威力。
memoization 一詞由 Donald Michie 依據拉丁語 memorandum 創造而來。它是一種將函數返回值快取起來的方法,原理非常簡單:把函數每次執行的結果存入一個鍵值對(視情況也可用陣列),在後續執行時,先在鍵值對中查找是否已有對應的結果,如果有就直接返回,沒有才真正執行函數體的求值部分。
很顯然,查找值——尤其是在鍵值對中查找——遠比執行函數快得多。現代 JavaScript 開發已經大量採用這一技術來優化效能。
我們知道,不同瀏覽器中 XMLHttpRequest 物件的實作方式各不相同,需要判斷瀏覽器型別以執行對應方法。這裡正是一個適合使用 memoization 的場景:
var createXHRObject = function(){
// 先把三種建立方式緩存起來
var methods = [
function(){ return new XMLHttpRequest(); },
function(){ return new ActiveXObject("Msxml2.XMLHTTP"); },
function(){ return new ActiveXObject("Microsoft.XMLHTTP"); }
];
for(var i=0, len=methods.length; i<len; i++){
try{
methods[i]();
}
catch(e){
continue; // 若拋出異常,則進入下一次循環
}
// 將 createXHRObject 指向能正常執行的方法,
// 以後再調用時就無需重複檢測瀏覽器
createXHRObject = methods[i];
return methods[i];
}
}
第一次執行 createXHRObject() 時,會循環嘗試 methods 中的方法,找到一個能正確執行的,並將 createXHRObject 的引用指向它。之後再使用時便無需判斷,直接取得正確方法即可。這在頻繁的 Ajax 調用中省去了重複的瀏覽器檢測開銷。
當然,這個範例的效能提升不算特別明顯,之所以列出來,是為了幫助你直觀理解 memoization 的實作方式。而在遞迴調用場景下,它的威力才會真正顯現。
先看經典的斐波那契序列:
function fib(n) {
if (n < 2) {
return n;
}
return fib(n - 1) + fib(n - 2);
}
這個看似簡潔的實作其實開銷驚人:fib(20) 會把 fib 執行 21891 次,而 fib(40) 更是高達 331160281 次!再看看如何用 memoization 改寫:
var iterMemoFib = (function() {
var cache = [1, 1];
var fib = function(n) {
if (n >= cache.length) {
// 將遞迴轉換為迭代,逐項填充快取
for (var i = cache.length; i <= n; i++) {
cache[i] = cache[i - 2] + cache[i - 1];
}
}
return cache[n-1];
}
return fib;
})();
透過快取已計算的結果,原本呈指數級增長的計算量被壓縮為線性,效能提升可謂天壤之別。
我們可以擴充 Function 的原型,加上 memoize 與 unmemoize 方法,這樣就能對任意函數實現記憶化與解除記憶化。當然,這種做法需謹慎——對一些並不頻繁執行的函數而言,快取反而多此一舉:
Function.prototype.memoize = function() {
var pad = {};
var self = this;
var obj = arguments.length > 0 ? arguments[i] : null;
var memoizedFn = function() {
// 把參數作為鍵、執行結果作為值快取起來
var args = [];
for (var i = 0; i < arguments.length; i++) {
args[i] = arguments[i];
}
if (!(args in pad)) {
pad[args] = self.apply(obj, arguments);
}
return pad[args];
}
memoizedFn.unmemoize = function() {
return self;
}
return memoizedFn;
}
Function.prototype.unmemoize = function() {
alert("Attempt to unmemoize an unmemoized function.");
return null;
}
使用方式非常簡單:
fib.memoize();
總的來說,memoization 是一種以空間換時間的經典優化手法。它尤其適合那些計算昂貴、且輸入重複率高的函數。掌握它,能讓你在面對效能瓶頸時多一件趁手的工具。