DIV CSS 佈局教程網

JavaScript 中的 Memoization 記憶化技術詳解
編輯:關於JavaScript     

近來閱讀《JavaScript 設計模式》一書時,注意到工廠模式中提到了 memoizing 技術。這個看似不起眼的概念,卻能在特定場景下大幅提升程式效能。本文將系統梳理 memoization 的原理與實作,並透過兩個經典範例帶你領略它的威力。

什麼是 Memoization

memoization 一詞由 Donald Michie 依據拉丁語 memorandum 創造而來。它是一種將函數返回值快取起來的方法,原理非常簡單:把函數每次執行的結果存入一個鍵值對(視情況也可用陣列),在後續執行時,先在鍵值對中查找是否已有對應的結果,如果有就直接返回,沒有才真正執行函數體的求值部分。

很顯然,查找值——尤其是在鍵值對中查找——遠比執行函數快得多。現代 JavaScript 開發已經大量採用這一技術來優化效能。

範例一:XHR 物件的建立

我們知道,不同瀏覽器中 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;
})();

透過快取已計算的結果,原本呈指數級增長的計算量被壓縮為線性,效能提升可謂天壤之別。

通用的 memoize 與 unmemoize

我們可以擴充 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();

參考文檔

  1. Memoizing functions in JavaScript
  2. JavaScript Memoization
  3. 提升 JS 性能:將遞歸轉換為迭代
  4. Memoization(維基百科)

總的來說,memoization 是一種以空間換時間的經典優化手法。它尤其適合那些計算昂貴、且輸入重複率高的函數。掌握它,能讓你在面對效能瓶頸時多一件趁手的工具。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved