動(dòng)態(tài)規(guī)劃之使用備忘錄來(lái)改進(jìn)Javascript函數(shù)
前言;
動(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ù)要使用備忘錄,需要滿足一定條件:它必須是引用透明的,即只有在調(diào)用函數(shù)的效果與用函數(shù)的返回值替換函數(shù)調(diào)用的效果完全相同的情況下才可以使用。
在Ruby、C++、Python等大多數(shù)編程語(yǔ)言中都有備忘錄,這些語(yǔ)言中甚至有很多庫(kù)可以簡(jiǎn)化。在本文中,我們將重點(diǎn)關(guān)注Javascript。編程語(yǔ)言或許不同,但其中的概念和思想是一致的。
備忘錄的概念
備忘錄需要理解以下兩個(gè)概念:
1.引用透明
如果一個(gè)表達(dá)式可以在不改變程序行為的情況下被其對(duì)應(yīng)的值替換(反之亦然),那么它就被稱為引用透明。這要求表達(dá)式必須是純的,即對(duì)于相同的輸入,表達(dá)式的值必須相同,并且它的求值必須沒(méi)有副作用。非引用透明的表達(dá)式稱為引用不透明。
有了上面的解釋,我們可以很快地把它和備忘錄的行為聯(lián)系起來(lái),這個(gè)概念讓我們可以寫出一個(gè)帶備忘錄的函數(shù)。
2.查找表
查找表(LUT)是一個(gè)數(shù)組,它用更為簡(jiǎn)單的數(shù)組索引操作取代運(yùn)行時(shí)計(jì)算。該過(guò)程被稱為“直接尋址”,LUT與哈希表的不同之處在于它檢索的是一個(gè)值。
比較函數(shù)使用備忘錄和不用備忘錄
以經(jīng)典的斐波那契數(shù)列定義為例:
function?Fibo(n)?{?? ???if?(n?<?2)?{?? ???????return?n;?? ???}?? ???return?Fibo(n?-?1)?+?Fibo(n?-?2);?? }?
你可能預(yù)料到了,一旦開(kāi)始使用大于20的數(shù)字,這個(gè)過(guò)程就會(huì)變得非常緩慢。而當(dāng)你處理35左右的數(shù)字時(shí),計(jì)算機(jī)估計(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;?? }();?
這部分有點(diǎn)麻煩,也不完全可讀,或者你也可以讓計(jì)算機(jī)來(lái)協(xié)助完成:
Fib?=?Fib.memoize();??
由于技術(shù)(瀏覽器安全策略)限制,備忘錄函數(shù)的參數(shù)只能是數(shù)組或標(biāo)量值,不能是對(duì)象。
下面的代碼擴(kuò)展了Function
對(duì)象以添加備忘錄功能。如果函數(shù)是一個(gè)方法,則可以將對(duì)象傳遞給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;?? };??
備忘錄的意義
- “記住”與某組特定輸入相對(duì)應(yīng)的結(jié)果
- 備忘錄降低了函數(shù)的時(shí)間成本以換取空間成本
- 備忘錄更不依賴機(jī)器
結(jié)論:什么是備忘錄?
在本文中,我們討論了備忘錄以及它的兩個(gè)主要概念:引用透明和查找表。此外,我們還探討了它對(duì)Javascript代碼的重要性,同時(shí)比較了未使用備忘錄的代碼和使用備忘錄的代碼之間的區(qū)別,并對(duì)緩存值所用的技術(shù)進(jìn)行了一定了解。
到此這篇關(guān)于動(dòng)態(tài)規(guī)劃之使用備忘錄來(lái)改進(jìn)Javascript函數(shù)的文章就介紹到這了,更多相關(guān)備忘錄改進(jìn)Javascript函數(shù)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
詳解微信小程序?qū)崿F(xiàn)WebSocket心跳重連
這篇文章主要介紹了詳解微信小程序?qū)崿F(xiàn)WebSocket心跳重連,小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2018-07-07淺談JavaScript 函數(shù)參數(shù)傳遞到底是值傳遞還是引用傳遞
下面小編就為大家?guī)?lái)一篇淺談JavaScript 函數(shù)參數(shù)傳遞到底是值傳遞還是引用傳遞。小編覺(jué)得挺不錯(cuò)的,現(xiàn)在就分享給大家,也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2016-08-08用JavaScript 判斷用戶使用的是 IE6 還是 IE7
判斷IE瀏覽器的腳本,方便根據(jù)瀏覽器不懂,支持不同的代碼的分別調(diào)用。2008-01-01利用js判斷手機(jī)是否安裝某個(gè)app的多種方案
這篇文章主要介紹了利用js檢測(cè)手機(jī)是否安裝某個(gè)app的多種方案,當(dāng)判斷后如果安裝了直接打開(kāi),如果有沒(méi)有安裝將自動(dòng)跳轉(zhuǎn)到下載的界面,有需要的朋友可以參考借鑒,下面來(lái)一起看看吧。2017-02-02firefox下input type="file"的size是多大
firefox對(duì)type="file" 的input的width定義目前是不支持的,但是FF支持size屬性,可以給size設(shè)置一個(gè)值,來(lái)控制上傳框的大小2011-10-10釘釘小程序web-view內(nèi)嵌H5頁(yè)面并實(shí)現(xiàn)通信
本文主要介紹了釘釘小程序web-view內(nèi)嵌H5頁(yè)面并實(shí)現(xiàn)通信,文中通過(guò)示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2022-05-05解決js中window.open彈出的是上次的緩存頁(yè)面問(wèn)題
本文為大家介紹下如何解決js中window.open彈出的是上次的緩存頁(yè)面的問(wèn)題,下面有個(gè)不錯(cuò)的示例,感興趣的額朋友可以參考下2013-12-12