DIV CSS 佈局教程網

JavaScript Memoization:用快取換效能的函式優化技巧
編輯:關於JavaScript     

從一個耗時函式說起

先看一段刻意磨磘 CPU 的程式:

var flower = function () {
    var t = 0, i = 0;
    for (; i < 5000000; i++) {
        t++;
    }
    return t;
};

它每次被呼叫都要重跑一遍五百萬次的迴圈,假設耗時 2~3 秒。問題來了:如果同樣的輸入被反覆要求計算,我們真的要一直重算嗎?

Memoization 是什麼

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];
    };
};

四個參數怎麼用

  • fn:要被包裝的原始函式。
  • cache:外部注入的快取物件,方便多個包裝函式共用或對外預先填充。
  • refetch:快取失效的哨兵值。當某個 key 的快取值恰好等於 refetch,就強制重算,可當成簡易的手動失效機制。
  • obj:指定 this 的指向,讓被包裝的方法能在正確的物件上下文執行。

實際套用

var fastFlower = Memoize(flower);

console.time('第一次');
fastFlower();          // 真的跑迴圈
console.timeEnd('第一次');

console.time('第二次');
fastFlower();          // 直接回傳快取
console.timeEnd('第二次');

第二次的耗時幾乎可以忽略不計。

使用時的注意事項

這個模式很好用,但不是萬靈丹:

  1. 只適合純函式。若函式結果會受外部狀態影響(例如讀取目前時間、隨機數、DOM 狀態),快取會傳回過期資料。
  2. key 的設計決定正確性。以 join('__') 串接參數時,若參數本身可能含 "__",就可能碰撞;物件型別參數也只會被轉成 [object Object]。
  3. 快取會無限長大。長期運行的應用建議加上 LRU 淘汰或大小上限,否則就是記憶體洩漏。
  4. refetch 的比較是寬鬆的 ==,型別不一致時行為可能出乎意料。

結論:Memoization 是把重複計算成本轉為一次性的空間成本,用在純粹、昂貴、重複呼叫頻繁的函式上,收益最直接。

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