萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 腳本程式專題 >> JavaScript

JavaScript 函數記憶化:首次執行後重寫自身實現極速快取

核心概念:函數記憶化

適用於純函數(相同輸入必得相同輸出、無副作用)、計算成本高、重複呼叫機率高的場景。首次執行完成後,將函數本身重寫為直接回傳快取結果的版本,後續呼叫零開銷。

經典實作模式

function expensiveCalculation(input) {
    // 模擬耗時運算
    const start = performance.now();
    while (performance.now() - start < 100) {} // 阻塞 100ms
    const result = input * 2; // 實際業務邏輯

    // 關鍵:重寫自身
    expensiveCalculation = function(cachedInput) {
        if (cachedInput === input) return result;
        // 若輸入不同,可選擇:拋錯、重新計算、或擴展為 Map 快取多組
        throw new Error('Memoized function called with different argument');
    };

    return result;
}

// 測試
console.time('第一次');
console.log(expensiveCalculation(42)); // 84,耗時 ~100ms
console.timeEnd('第一次');

console.time('第二次');
console.log(expensiveCalculation(42)); // 84,耗時 ~0ms
console.timeEnd('第二次');

通用記憶化高階函式(支援多參數、多組快取)

/**
 * 建立記憶化版本的函數
 * @param {Function} fn - 目標函數
 * @param {Function} [keyGenerator] - 自訂快取鍵生成器,預設 JSON.stringify
 * @returns {Function} 記憶化後的函數
 */
function memoize(fn, keyGenerator = (...args) => JSON.stringify(args)) {
    const cache = new Map();
    return function(...args) {
        const key = keyGenerator(...args);
        if (cache.has(key)) {
            return cache.get(key);
        }
        const result = fn.apply(this, args);
        cache.set(key, result);
        return result;
    };
}

// 使用範例
const fib = memoize(function fibonacci(n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2); // 遞迴也會命中快取
});

console.time('fib(40)');
console.log(fib(40)); // 102334155,瞬間完成
console.timeEnd('fib(40)');

console.time('fib(40) 二次');
console.log(fib(40)); // 直接從快取取得
console.timeEnd('fib(40) 二次');

進階:LRU 快取淘汰(防止記憶體無限增長)

function memoizeLRU(fn, maxSize = 100) {
    const cache = new Map(); // Map 保持插入順序
    return function(...args) {
        const key = JSON.stringify(args);
        if (cache.has(key)) {
            // 移至最新(LRU)
            const val = cache.get(key);
            cache.delete(key);
            cache.set(key, val);
            return val;
        }
        const result = fn.apply(this, args);
        cache.set(key, result);
        if (cache.size > maxSize) {
            // 刪除最舊
            const firstKey = cache.keys().next().value;
            cache.delete(firstKey);
        }
        return result;
    };
}

適用場景與不適用場景

適用 ✅不適用 ❌
昂貴的純計算(遞迴、DP、大數運算)有副作用(寫 DB、發 API、修改 DOM)
相同參數高頻呼叫參數每次都不同(如隨機數、時間戳)
格式化/解析/轉換函式依賴外部可變狀態(如當前用戶、當前時間)
React/Vue computed 內部邏輯需即時反映最新狀態的函數

React/Vue 整合範例

// React: useMemo 內部原理類似
const memoizedValue = useMemo(() => expensiveCompute(a, b), [a, b]);

// Vue: computed 自動依賴追蹤 + 快取
computed: {
    filteredList() {
        return this.list.filter(item => item.name.includes(this.keyword));
    }
}

原文碼重構說明

原文使用 Date.now() 迴圈模擬耗時、函數重寫為無參數版本(僅支援單一固定輸入)。現代寫法改用 performance.now()、高階函式 memoize 支援多參數、Map 快取、可選 LRU 淘汰,通用性大幅提升。

copyright © 萬盛學電腦網 all rights reserved