JavaScript 高級技巧 Memoization

劉德剛發布于2019-08-23 12:22 / 1696人閱讀

摘要：來源于拉丁語，不要與混淆了。本文首先介紹一個簡單的使用優化技術的例子，然后解讀和庫中使用的源碼，加深理解?？偨Y是一種優化技術，避免一些不必要的重復計算，可以提高計算速度。

memoization 來源于拉丁語 memorandum ("to be remembered")，不要與 memorization 混淆了。

首先來看一下維基百科的描述：

In computing, memoization or memoisation is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.

簡單來說，memoization 是一種優化技術，主要用于通過存儲昂貴的函數調用的結果來加速計算機程序，并在再次發生相同的輸入時返回緩存的結果。

本文首先介紹一個簡單的使用 memoization 優化技術的例子，然后解讀 underscore 和 reselect 庫中使用 memoization 的源碼，加深理解。

階乘 不使用 memoization

不假思索，我們會立即寫下如下的代碼：

const factorial = n => {
    if (n === 1) {
        return 1
    } else {
        return factorial(n - 1) * n
    }
};

使用 memoization

const cache = []
const factorial = n => {
    if (n === 1) {
        return 1
    } else if (cache[n - 1]) {
        return cache[n - 1]
    } else {
        let result = factorial(n - 1) * n
        cache[n - 1] = result
        return result
    }
};

使用閉包和 memoization

常見的方式是閉包和 memoization 一起搭配使用：

const factorialMemo = () => {
    const cache = []
    const factorial = n => {
        if (n === 1) {
            return 1
        } else if (cache[n - 1]) {
            console.log(`get factorial(${n}) from cache...`)
            return cache[n - 1]
        } else {
            let result = factorial(n - 1) * n
            cache[n - 1] = result
            return result
        }
    }
    return factorial
};
const factorial = factorialMemo();

繼續變形,下面這種編寫方式是最常見的形式。

const factorialMemo = func => {
    const cache = []
    return function(n) {
        if (cache[n - 1]) {
            console.log(`get factorial(${n}) from cache...`)
            return cache[n - 1]
        } else {
            const result = func.apply(null, arguments)
            cache[n - 1] = result
            return result
        }
    }
}

const factorial = factorialMemo(function(n) {
    return n === 1 ? 1 : factorial(n - 1) * n
});

從階乘的這個例子可以知道 memoization 是一個空間換時間的方式，存儲執行結果，下次再次發生相同的輸入會直接輸出結果，提高了執行的速度。

underscore 源碼中的 memoization

// Memoize an expensive function by storing its results.
_.memoize = function(func, hasher) {
    var memoize = function(key) {
        var cache = memoize.cache;
        var address = "" + (hasher ? hasher.apply(this, arguments) : key);
        if (!_.has(cache, address)) cache[address] = func.apply(this, arguments);
        return cache[address];
    };
    memoize.cache = {};
    return memoize;
};

代碼一目了然，使用 _.memoize 來實現階乘如下：

const factorial = _.memoize(function(n) {
    return n === 1 ? 1 : factorial(n - 1) * n
});

參照這個源碼，上面的階乘繼續可以變形如下：

const factorialMemo = func => {
    const memoize = function(n) {
        const cache = memoize.cache
        if (cache[n - 1]) {
            console.log(`get factorial(${n}) from cache...`)
            return cache[n - 1]
        } else {
            const result = func.apply(null, arguments)
            cache[n - 1] = result
            return result
        }
    }
    memoize.cache = []
    return memoize
}

const factorial = factorialMemo(function(n) {
    return n === 1 ? 1 : factorial(n - 1) * n
});

reselect 源碼中的 memoization

export function defaultMemoize(func, equalityCheck = defaultEqualityCheck) {
    let lastArgs = null
    let lastResult = null
    // we reference arguments instead of spreading them for performance reasons
    return function () {
        if (!areArgumentsShallowlyEqual(equalityCheck, lastArgs, arguments)) {
            // apply arguments instead of spreading for performance.
            lastResult = func.apply(null, arguments)
        }

        lastArgs = arguments
        return lastResult
    }
};

從源碼可以知道當 lastArgs 與 arguments 相同的時候，就不會再執行 func。

總結

memoization 是一種優化技術，避免一些不必要的重復計算，可以提高計算速度。

參考

Memoization wiki

Understanding JavaScript Memoization In 3 Minutes

Underscore

reselect

Implementing Memoization in JavaScript

GPU云服務器云服務器高級顯示技巧 JAVASCRIPT技巧 javascript七大技巧 javascript調試技巧

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/98395.html

Memoization in JavaScript

摘要：源碼函數調用過，沒有變化，參數時返回緩存值。而通過，可以把上一次的計算結果保存下來，而避免重復計算。這意味著將跳過渲染組件，并重用最后渲染的結果。 1. 基本概念在一個CPU密集型應用中，我們可以使用Memoization來進行優化，其主要用于通過存儲昂貴的函數調用的結果來加速程序，并在再次發生相同的輸入時返回緩存的結果。例如一個簡單的求平方根的函數： const sqrt = Ma...

ccj659 2019-08-23 17:13 評論0 收藏0
斐波那契數列求和的js方案以及優化

摘要：在上做了一道斐波那契數列求和的題目，做完之后做了一些簡單的優化和用另一種方法實現。動態規劃解決方案斐波那契數列求和除了可以用遞歸的方法解決，還可以用動態規劃的方法解決。在codewars上做了一道斐波那契數列求和的題目，做完之后做了一些簡單的優化和用另一種方法實現。題目 function fibonacci(n) { if(n==0 || n == 1) r...

xinhaip 2019-08-20 11:35 評論0 收藏0
Python 應用剖析工具介紹

摘要：免責聲明不要過早地進行優化有關過早優化的詳細分析請查閱本文。如果在龐大的應用中運行該分析工具，會得到一張巨大的圖片。免責聲明請確保該方法只用于函數如果將記憶用于帶有副作用譬如的函數，緩存可能無法達到預期的效果。【編者按】本文作者為來自 HumanGeo 的工程師 Davis，主要介紹了用于 Python 應用性能分析的幾個工具。由國內 ITOM 管理平臺 OneAPM 編譯呈現。在...

lanffy 2019-07-25 10:18 評論0 收藏0
JS專題之memoization

摘要：前言在計算機領域，記憶是主要用于加速程序計算的一種優化技術，它使得函數避免重復演算之前已被處理過的輸入，而返回已緩存的結果。被執行了不是素數，其他數字默認是素數。我們可以看出，如果從開始打印斐波那契數列，函數被執行了次。前言在計算機領域，記憶（memoization）是主要用于加速程序計算的一種優化技術，它使得函數避免重復演算之前已被處理過的輸入，而返回已緩存的結果。 -- wi...

zhisheng 2019-08-23 15:08 評論0 收藏0
【譯】你可能不需要派生狀態

摘要：所有派生狀態導致的問題無異于兩種無條件的根據來更新無論和是否匹配來更新。派生狀態最常見的錯誤就是將這兩者混和在一起。因此通常被用于性能優化而不是來判斷派生狀態的正確性。我們可以使用派生狀態來存儲過濾列表這種方式避免了重新計算。原文鏈接：https://reactjs.org/blog/2018... 翻譯這篇文章的起因是因為在一次需求迭代中錯誤的使用了getDerivedState...

dinfer 2019-08-23 13:39 評論0 收藏0