欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

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

 更新時間:2022年04月07日 10:09:10   作者:盧鑫旺  
這篇文章主要介紹了動態(tài)規(guī)劃之使用備忘錄來改進(jìn)Javascript函數(shù),動態(tài)規(guī)劃它既是一種數(shù)學(xué)優(yōu)化方法,也是一種計算機(jī)編程方法,下文相關(guān)資料介紹需要的小伙伴可以參考一下

前言;

動態(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.引用透明

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

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

2.查找表

查找表(LUT)是一個數(shù)組,它用更為簡單的數(shù)組索引操作取代運行時計算。該過程被稱為“直接尋址”,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?<=?n;?i++)?{??
???????????????cache[i]?=?cache[i?-?2]?+?cache[i?-?1];??
???????????}??
???????}??
???????return?cache[n];??
???}??

??return?fib;??
}();?

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

Fib?=?Fib.memoize();??

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

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

Function.prototype.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;??
};??
???
Function.prototype.unmemoize?=?function?()?{??
?alert("Attempt?to?unmemoize?an?unmemoized?function.");??
?return?null;??
};??

備忘錄的意義

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

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

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

到此這篇關(guān)于動態(tài)規(guī)劃之使用備忘錄來改進(jìn)Javascript函數(shù)的文章就介紹到這了,更多相關(guān)備忘錄改進(jìn)Javascript函數(shù)內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

最新評論