動態規劃：使用備忘錄來改進Javascript函數

作者：盧鑫旺 2022-04-07 08:00:00

本文將介紹什么是備忘錄，備忘錄對Javascript開發人員來說具有哪些價值，以及如何使用它來改進Javascript函數，從而對備忘錄本身以及備忘錄對優化應用程序的意義有一個深入了解。

譯者 | 盧鑫旺

審校 | 梁策孫淑娟

動態規劃已出現了十多年。根據維基百科，它既是一種數學優化方法，也是一種計算機編程方法。一個問題要真正應用動態規劃，必須具有兩個關鍵屬性：最優結構和重疊子結構。本文不會細講動態規劃，而是將關注重疊子結構如何成為動態規劃的關鍵屬性之一。由于這關系到接下來的存儲解決方案問題，所以對它的討論非常重要。

在本文中，我們將討論以下幾個主題：

什么是備忘錄
備忘錄的主要概念
函數使用備忘錄和不用備忘錄的比較
備忘錄的意義

什么是備忘錄?

備忘錄是緩存的一種形式，是一種方便進入和后續使用的值存儲方法。備忘錄是將已解決問題的結果記錄下來，這樣下次需要再次執行相同操作時，就不必重新計算了。不過，一個函數要使用備忘錄，需要滿足一定條件：它必須是引用透明的，即只有在調用函數的效果與用函數的返回值替換函數調用的效果完全相同的情況下才可以使用。

在Ruby、C++、Python等大多數編程語言中都有備忘錄，這些語言中甚至有很多庫可以簡化。在本文中，我們將重點關注Javascript。編程語言或許不同，但其中的概念和思想是一致的。

備忘錄的概念

備忘錄需要理解以下兩個概念：

1.引用透明

2.查找表

1.引用透明

如果一個表達式可以在不改變程序行為的情況下被其對應的值替換(反之亦然)，那么它就被稱為引用透明。這要求表達式必須是純的，即對于相同的輸入，表達式的值必須相同，并且它的求值必須沒有副作用。非引用透明的表達式稱為引用不透明。

有了上面的解釋，我們可以很快地把它和備忘錄的行為聯系起來，這個概念讓我們可以寫出一個帶備忘錄的函數。

2.查找表

查找表(LUT)是一個數組，它用更為簡單的數組索引操作取代運行時計算。該過程被稱為“直接尋址”，LUT與哈希表的不同之處在于它檢索的是一個值。

比較函數使用備忘錄和不用備忘錄

以經典的斐波那契數列定義為例：

1.function Fibo(n) {  
2.    if (n < 2) {  
3.        return n;  
4.    }  
5.    return Fibo(n - 1) + Fibo(n - 2);  
6.}

你可能預料到了，一旦開始使用大于20的數字，這個過程就會變得非常緩慢。而當你處理35左右的數字時，計算機估計也撐不住了。

解決方法是記錄調用函數的返回結果

1.var IterMemoFib = function() {  
2.    var cache = [1, 1];  
3.    var fib = function(n) {  
4.        if (n >= cache.length) {  
5.            for (var i = cache.length; i <= n; i++) {  
6.                cache[i] = cache[i - 2] + cache[i - 1];  
7.            }  
8.        }  
9.        return cache[n];  
10.    }  
11.  
12.    return fib;  
13.}();

這部分有點麻煩，也不完全可讀，或者你也可以讓計算機來協助完成：

1.Fib = Fib.memoize();

由于技術(瀏覽器安全策略)限制，備忘錄函數的參數只能是數組或標量值，不能是對象。

下面的代碼擴展了Function對象以添加備忘錄功能。如果函數是一個方法，則可以將對象傳遞給memoize()。

1.Function.prototype.memoize = function () {  
2. var pad = {};  
3. var self = this;  
4. var obj = arguments.length > 0 ? arguments[i] : null;  
5.   
6. var memoizedFn = function () {  
7.   // Copy the arguments object into an array: allows it to be used as  
8.   // a cache key.  
9.   var args = [];  
10.   for (var i = 0; i < arguments.length; i++) {  
11.     args[i] = arguments[i];  
12.   }  
13.   
14.   // Evaluate the memoized function if it hasn't been evaluated with  
15.   // these arguments before.  
16.   if (!(args in pad)) {  
17.     pad[args] = self.apply(obj, arguments);  
18.   }  
19.   
20.   return pad[args];  
21. };  
22.   
23. memoizedFn.unmemoize = function () {  
24.   return self;  
25. };  
26.   
27. return memoizedFn;  
28.};  
29.   
30.Function.prototype.unmemoize = function () {  
31. alert("Attempt to unmemoize an unmemoized function.");  
32. return null;  
33.};

備忘錄的意義

“記住”與某組特定輸入相對應的結果
備忘錄降低了函數的時間成本以換取空間成本
備忘錄更不依賴機器

結論：什么是備忘錄?

在本文中，我們討論了備忘錄以及它的兩個主要概念：引用透明和查找表。此外，我們還探討了它對Javascript代碼的重要性，同時比較了未使用備忘錄的代碼和使用備忘錄的代碼之間的區別，并對緩存值所用的技術進行了一定了解。

以下是一些可使用備忘錄的Javascript庫，如有需要可供參考：

https://developer.yahoo.com/yui/3/cache/

https://github.com/planttheidea/micro-memoize

https://github.com/caiogondim/fast-memoize.js

https://lodash.com/docs/4.17.15#memoize

譯者介紹

盧鑫旺，51CTO社區編輯，半路出家的九零后程序員。做過前端頁面，寫過業務接口，搞過爬蟲，研究過JS，有幸接觸Golang，參與微服務架構轉型。目前主寫Java，負責公司可定制化低代碼平臺的數據引擎層設計開發工作。

原文標題：??Dynamic Programming: Using Memoization to Improve Your Javascript Functions??，作者：Ignatius Sani

責任編輯：華軒來源： 51CTO

Javascript 開發