譯者 | 盧鑫旺
審校 | 梁策 孫淑娟
動態(tài)規(guī)劃已出現(xiàn)了十多年。根據(jù)維基百科，它既是一種數(shù)學(xué)優(yōu)化方法，也是一種計算機(jī)編程方法。一個問題要真正應(yīng)用動態(tài)規(guī)劃，必須具有兩個關(guān)鍵屬性：最優(yōu)結(jié)構(gòu)和重疊子結(jié)構(gòu)。本文不會細(xì)講動態(tài)規(guī)劃，而是將關(guān)注重疊子結(jié)構(gòu)如何成為動態(tài)規(guī)劃的關(guān)鍵屬性之一。由于這關(guān)系到接下來的存儲解決方案問題，所以對它的討論非常重要。
本文將介紹什么是備忘錄，備忘錄對Javascript開發(fā)人員來說具有哪些價值，以及如何使用它來改進(jìn)Javascript函數(shù)，從而對備忘錄本身以及備忘錄對優(yōu)化應(yīng)用程序的意義有一個深入了解。
在本文中，我們將討論以下幾個主題：
- 什么是備忘錄
- 備忘錄的主要概念
- 函數(shù)使用備忘錄和不用備忘錄的比較
- 備忘錄的意義
什么是備忘錄?
備忘錄是緩存的一種形式，是一種方便進(jìn)入和后續(xù)使用的值存儲方法。備忘錄是將已解決問題的結(jié)果記錄下來，這樣下次需要再次執(zhí)行相同操作時，就不必重新計算了。不過，一個函數(shù)要使用備忘錄，需要滿足一定條件：它必須是引用透明的，即只有在調(diào)用函數(shù)的效果與用函數(shù)的返回值替換函數(shù)調(diào)用的效果完全相同的情況下才可以使用。
在Ruby、C++、Python等大多數(shù)編程語言中都有備忘錄，這些語言中甚至有很多庫可以簡化。在本文中，我們將重點關(guān)注Javascript。編程語言或許不同，但其中的概念和思想是一致的。
備忘錄的概念
備忘錄需要理解以下兩個概念：
1.引用透明
2.查找表
1.引用透明
如果一個表達(dá)式可以在不改變程序行為的情況下被其對應(yīng)的值替換(反之亦然)，那么它就被稱為引用透明。這要求表達(dá)式必須是純的，即對于相同的輸入，表達(dá)式的值必須相同，并且它的求值必須沒有副作用。非引用透明的表達(dá)式稱為引用不透明。
有了上面的解釋，我們可以很快地把它和備忘錄的行為聯(lián)系起來，這個概念讓我們可以寫出一個帶備忘錄的函數(shù)。
2.查找表
查找表(LUT)是一個數(shù)組，它用更為簡單的數(shù)組索引操作取代運行時計算。該過程被稱為“直接尋址”，LUT與哈希表的不同之處在于它檢索的是一個值。
比較函數(shù)使用備忘錄和不用備忘錄
以經(jīng)典的斐波那契數(shù)列定義為例：
1.function Fibo(n) {
2. if (n < 2) {
3. return n;
4. }
5. return Fibo(n - 1) + Fibo(n - 2);
6.}
你可能預(yù)料到了，一旦開始使用大于20的數(shù)字，這個過程就會變得非常緩慢。而當(dāng)你處理35左右的數(shù)字時，計算機(jī)估計也撐不住了。
解決方法是記錄調(diào)用函數(shù)的返回結(jié)果
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.}();
這部分有點麻煩，也不完全可讀，或者你也可以讓計算機(jī)來協(xié)助完成：
1.Fib = Fib.memoize();
由于技術(shù)(瀏覽器安全策略)限制，備忘錄函數(shù)的參數(shù)只能是數(shù)組或標(biāo)量值，不能是對象。
下面的代碼擴(kuò)展了Function對象以添加備忘錄功能。如果函數(shù)是一個方法，則可以將對象傳遞給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.};
備忘錄的意義
- “記住”與某組特定輸入相對應(yīng)的結(jié)果
- 備忘錄降低了函數(shù)的時間成本以換取空間成本
- 備忘錄更不依賴機(jī)器
結(jié)論：什么是備忘錄?
在本文中，我們討論了備忘錄以及它的兩個主要概念：引用透明和查找表。此外，我們還探討了它對Javascript代碼的重要性，同時比較了未使用備忘錄的代碼和使用備忘錄的代碼之間的區(qū)別，并對緩存值所用的技術(shù)進(jìn)行了一定了解。
以下是一些可使用備忘錄的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社區(qū)編輯，半路出家的九零后程序員。做過前端頁面，寫過業(yè)務(wù)接口，搞過爬蟲，研究過JS，有幸接觸Golang，參與微服務(wù)架構(gòu)轉(zhuǎn)型。目前主寫Java，負(fù)責(zé)公司可定制化低代碼平臺的數(shù)據(jù)引擎層設(shè)計開發(fā)工作。
原文標(biāo)題：??Dynamic Programming: Using Memoization to Improve Your Javascript Functions??，作者：Ignatius Sani
