審校 | 梁策 孫淑娟

成都創(chuàng)新互聯(lián)于2013年開(kāi)始，公司以網(wǎng)站制作、成都網(wǎng)站設(shè)計(jì)、系統(tǒng)開(kāi)發(fā)、網(wǎng)絡(luò)推廣、文化傳媒、企業(yè)宣傳、平面廣告設(shè)計(jì)等為主要業(yè)務(wù)，適用行業(yè)近百種。服務(wù)企業(yè)客戶(hù)上千余家，涉及國(guó)內(nèi)多個(gè)省份客戶(hù)。擁有多年網(wǎng)站建設(shè)開(kāi)發(fā)經(jīng)驗(yàn)。為企業(yè)提供專(zhuān)業(yè)的網(wǎng)站建設(shè)、創(chuàng)意設(shè)計(jì)、宣傳推廣等服務(wù)。 通過(guò)專(zhuān)業(yè)的設(shè)計(jì)、獨(dú)特的風(fēng)格，為不同客戶(hù)提供各種風(fēng)格的特色服務(wù)。

動(dòng)態(tài)規(guī)劃已出現(xiàn)了十多年。根據(jù)維基百科，它既是一種數(shù)學(xué)優(yōu)化方法，也是一種計(jì)算機(jī)編程方法。一個(gè)問(wèn)題要真正應(yīng)用動(dòng)態(tài)規(guī)劃，必須具有兩個(gè)關(guān)鍵屬性：最優(yōu)結(jié)構(gòu)和重疊子結(jié)構(gòu)。本文不會(huì)細(xì)講動(dòng)態(tài)規(guī)劃，而是將關(guān)注重疊子結(jié)構(gòu)如何成為動(dòng)態(tài)規(guī)劃的關(guān)鍵屬性之一。由于這關(guān)系到接下來(lái)的存儲(chǔ)解決方案問(wèn)題，所以對(duì)它的討論非常重要。

本文將介紹什么是備忘錄，備忘錄對(duì)Javascript開(kāi)發(fā)人員來(lái)說(shuō)具有哪些價(jià)值，以及如何使用它來(lái)改進(jìn)Javascript函數(shù)，從而對(duì)備忘錄本身以及備忘錄對(duì)優(yōu)化應(yīng)用程序的意義有一個(gè)深入了解。

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

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

什么是備忘錄?

備忘錄是緩存的一種形式，是一種方便進(jìn)入和后續(xù)使用的值存儲(chǔ)方法。備忘錄是將已解決問(wèn)題的結(jié)果記錄下來(lái)，這樣下次需要再次執(zhí)行相同操作時(shí)，就不必重新計(jì)算了。不過(guò)，一個(gè)函數(shù)要使用備忘錄，需要滿(mǎn)足一定條件：它必須是引用透明的，即只有在調(diào)用函數(shù)的效果與用函數(shù)的返回值替換函數(shù)調(diào)用的效果完全相同的情況下才可以使用。

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

備忘錄的概念

備忘錄需要理解以下兩個(gè)概念：

1.引用透明

2.查找表

1.引用透明

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

有了上面的解釋?zhuān)覀兛梢院芸斓匕阉蛡渫浀男袨槁?lián)系起來(lái)，這個(gè)概念讓我們可以寫(xiě)出一個(gè)帶備忘錄的函數(shù)。

2.查找表

查找表(LUT)是一個(gè)數(shù)組，它用更為簡(jiǎn)單的數(shù)組索引操作取代運(yùn)行時(shí)計(jì)算。該過(guò)程被稱(chēng)為“直接尋址”，LUT與哈希表的不同之處在于它檢索的是一個(gè)值。

比較函數(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ù)料到了，一旦開(kāi)始使用大于20的數(shù)字，這個(gè)過(guò)程就會(huì)變得非常緩慢。而當(dāng)你處理35左右的數(shù)字時(shí)，計(jì)算機(jī)估計(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.}(); 

這部分有點(diǎn)麻煩，也不完全可讀，或者你也可以讓計(jì)算機(jī)來(lái)協(xié)助完成：

1.Fib = Fib.memoize();  

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

下面的代碼擴(kuò)展了Function對(duì)象以添加備忘錄功能。如果函數(shù)是一個(gè)方法，則可以將對(duì)象傳遞給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.};  

備忘錄的意義

• “記住”與某組特定輸入相對(duì)應(yīng)的結(jié)果
• 備忘錄降低了函數(shù)的時(shí)間成本以換取空間成本
• 備忘錄更不依賴(lài)機(jī)器

結(jié)論：什么是備忘錄?

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

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

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

譯者介紹

盧鑫旺，社區(qū)編輯，半路出家的九零后程序員。做過(guò)前端頁(yè)面，寫(xiě)過(guò)業(yè)務(wù)接口，搞過(guò)爬蟲(chóng)，研究過(guò)JS，有幸接觸Golang，參與微服務(wù)架構(gòu)轉(zhuǎn)型。目前主寫(xiě)Java，負(fù)責(zé)公司可定制化低代碼平臺(tái)的數(shù)據(jù)引擎層設(shè)計(jì)開(kāi)發(fā)工作。

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

分享文章：動(dòng)態(tài)規(guī)劃：使用備忘錄來(lái)改進(jìn)Javascript函數(shù)
URL網(wǎng)址：http://uogjgqi.cn/article/dpdooio.html