動態(tài)規(guī)劃之使用備忘錄來改進(jìn)Javascript函數(shù)

第動態(tài)規(guī)劃之使用備忘錄來改進(jìn)Javascript函數(shù)目錄什么是備忘錄備忘錄的概念1.引用透明2.查找表比較函數(shù)使用備忘錄和不用備忘錄解決方法是記錄調(diào)用函數(shù)的返回結(jié)果備忘錄的意義結(jié)論：什么是備忘錄前言;

動態(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ù)編程語言中都有備忘錄，這些語言中甚至有很多庫可以簡化。在本文中，我們將重點(diǎn)關(guān)注Javascript。編程語言或許不同，但其中的概念和思想是一致的。

備忘錄的概念

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

1.引用透明

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

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

2.查找表

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

比較函數(shù)使用備忘錄和不用備忘錄

以經(jīng)典的斐波那契數(shù)列定義為例：

function

Fibo(n)

{

if

(n

2)

{

return

n;

}

return

Fibo(n

-

1)

+

Fibo(n

-

2);

}

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

解決方法是記錄調(diào)用函數(shù)的返回結(jié)果

var

IterMemoFib

=

function()

{

var

cache

=

[1,

1];

var

fib

=

function(n)

{

if

(n

=

cache.length)

{

for

(var

i

=

cache.length;

i

i++)

{

cache[i]

=

cache[i

-

2]

+

cache[i

-

1];

}

}

return

cache[n];

}

return

fib;

}();

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

Fib

=

Fib.memoize();

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

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

Ftotype.memoize

=

function

()

{

var

pad

=

{};

var

self

=

this;

var

obj

=

arguments.length

0

arguments[i]

:

null;

var

memoizedFn

=

function

()

{

//

Copy

the

arguments

object

into

an

array:

allows

it

to

be

used

as

//

a

cache

key.

var

args

=

[];

for

(var

i

=

0;

i

arguments.length;

i++)

{

args[i]

=

arguments[i];

}

//

Evaluate

the

memoized

function

if

it

hasn't

been

evaluated

with

//

these

arguments

before.

if

(!(args

in

pad))

{

pad[args]

=

self.apply(obj,

arguments);

}

return

pad[args];

memoizedFn.unmemoize

=

function

()

{

return

self;

};

return

memoizedFn;

Ftotype.unmemoize

=

function

()

{

alert("Attempt

to

unmemoize

an

unmemoized

function.");

return

null;

};

備忘錄的意義

記住與某組特定輸入相對應(yīng)的結(jié)果備忘錄降低了函數(shù)的時間成本以換取空間成本備忘錄更不