Мемоизација у рачунарству, је техника оптимизације која се најпре користи да би се убрзало извршавање рачунарских програма тако што се складиште резултати „скупих“ позива функција и враћају кеширани резултат када се поново јаве исти улази. Мемоизација се такође користи у другим контекстима (и за потребе које се не односе на убрзавање рачунарских програма), као што је у једноставној узајамној рекурзији опадајуће парсирање.. у општем топ-даун (одозго-надоле) алгоритмуFrost, Richard, Hafiz, Rahmatullah, and Callaghan, Paul. , Pages: 109 – 120,, Prague.Frost, Richard, Hafiz, Rahmatullah, and Callaghan, Paul. /2008, Pages: 167–181,, San Francisco. за парсирање, који прилагођава двосмисленост и леву рекурзију у полиномиалном времену и простору. Иако је везана за кеширање, мемоизација указује на специфичан случај ове оптимизације, разликовајући је од облика кеширања као што су баферовање или замена страница. У контексту неких логичких програмских језика, мемоизација је такође позната као табелирање;Warren, David. "Tabling and Datalog Programming". Accessed 29 May 2009. погледати такође лукап табеле.
Етимологија
Термин „мемоизација“ је увео Доналд Мичи (Donald Michie) 1968. године и изведен је од латинске речи „memorandum“ („бити запамћен“), која се у Енглеском језику скраћено „memo“ и има значење „претварати резултате функција у нешто што ће бити запамћено“. Термин „мемоизација“ може да се помеша са термином „меморизација“, јер су етимолошки сродни. Међутим, „мемоизација“ има специфично значење у рачунарству.
Преглед Мемоизациона функција „памти“ резултате који одговарају неком скупу специфичних улаза. Накнадни позиви са сачуваним улазима ће пре враћати сачувани резултат него рачунати га опет и тако елиминишу првобитну цену позива функције са задатим параметрима за све, осим за први позив. Скуп сачуваних асоцијација могу имати фиксну величину којим управља алгоритам замене или фиксни скуп, у зависности од природе функције и њене употребе. Функција може бити мемоизована само ако је референциално транспарентна; то значи само ако позив функције има у потпуности исти ефекат као и замена позива функције са својом повратном вредношћу. (Међутим, постоје изузеци.) Док су повезани са лукап табелама, с' обзиром да мемоизација често користи такве табеле у својој имплементацији, мемоизација попуњава кеш са резултатима транспарентно у току извршења, ако је потребно, пре него унапред. Мемоизација је начин на који се смањује трошак времена извршења функције у замену за трошак меморијског простора; што значи да мемоизоване фукнције постају оптимизоване по брзини на рачун већег коришћења меморијског простора рачунара. Трошак време/простор алгоритма има спцифично име у рачунарству: теорија рачунарске комплексност. Све фукнције имају рачунарску комплексност у времену (тј. време потребно да се функција изврши) и у меморијском простору. Иако се компромис јавља (нпр коришћени меморијски простор у односу на убрзање) ово се разликује од неких других оптимизација које укључују време-простор компромис, као што је смањење цене операција, у томе што се мемоизација изводи у фази извршења програма, а не у фази компилације. Штавише, смањење цене операција потенцијално замењује скупу операцију, као што је множење са мање скупом операцијом, као што је сабирање, и резултати уштеде могу бити веома зависни од рачунара, тако да нису портабилне између различитих рачунара, док је мемоизација више независна од рачунара - крос-платформ стратегија. Размотрити следећи псеудокод фукнције за израчунавање факторијела од n:
function factorial (n is a non-negative integer) if n is 0 then return 1 [by the convention that 0! = 1] else return factorial(n – 1) times n [recursively invoke factorial with the parameter 1 less than n] end if end function
За сваки цео број n такав да је n≥0, крајњи резултат функције factorial је инваријантан; ако се позива као x = factorial(3), резултат ће бити такав да ће x увек бити додељена вредност 6. Немемоизована верзија горње функције, због природе рекурзивног алгоритма који је коришћен, захтеваће n + 1 позива функције факторијел да дође до резултата, и сваки позив има трошкове у времену за које је потребно да функција врати израчунату вредност. У зависности од рачунара, трошак може бити сума следећих трошкова: поставки стека позива фукнције. поређења n са 0. одузимања 1 од n. постављања стека за рекурзивне позиве. множења резултата рекурзивног позива функције факторијел са n. меморисања повратне вредности тако да може бити коришћена у контесту позива.
У немомизованој имплементацији, сваки први позив функције factorial укључује кумулативне трошкове корака 2 до 6, који су пропорционални иницијалној вредности n.
Мемоизована верзија функције factorial следи:
function factorial (n is a non-negative integer) if n is 0 then return 1 [by the convention that 0! = 1] else if n is in lookup-table then return lookup-table-value-for-n else let x = factorial(n – 1) times n [recursively invoke factorial with the parameter 1 less than n] store x in lookup-table in the nth slot [remember the result of n! for later] return x end if end function
У конкретном примеру, ако се функција факторијел први пут позове са бројем 5 и ако се касније позове са било којим бројем који је мањи или једнак броју 5, те повратне вредности ће бити мемоизоване, зато што је функција факторијел била рекурзивно позивана са вредношћима 5, 4, 3, 2, 1 и 0 и повратна вредност за сваки од тих позива је била ускладиштена. Ако је касније позвана са бројевима већим од 5, нпр. 7, биће направљена само 2 рекурзивна позива (7 и 6), а вредност за 5! је већ складиштена од претходног позива. На тај начин мемоизација омогућава да функција постане ефикаснија у времену извршења, што се више позива. То коначно доприноси општем убрзању извршења функције.
Остала разматрања Функционално програмирање Мемоизација се много користи у компајлерима за функционалне програмске језике, који често користе стратегију еваулације позива по имену. Да би избегли допунске трошкове везане за израчунавање вредности аргумената, компајлери за ове језике често користе помоћне функције које се зову танкови (претварачи) да би израчунали вредности аргумента и мемоизовали ове функције да би се избегло поновно израчунавање.
Аутоматска мемоизација
Док мемоизација може да буде придружена функцијама интерно и експлицитно од стране програмера, на исти такав начин горе поменута мемоизована функција факторијел може да буде аутоматски мемоизована екстерно. Технике које је користио Петер Норвиг (Peter Norvig) имају примену, не само у Лиспу (језик у коме је представио аутоматску мемизацију), него и у другим програмским језицима. Примена аутоматске мемоизације су формално истражене и у студијама преписивања термина , H. Kirchner and G. Levi . стр. 128–142, Volterra, Italy, . и вештачкој интелигенцији.Mayfield, James, et al., Using Automatic Memoization as a Software Engineering Tool in Real-World AI Systems, Proceedings of the Eleventh IEEE Conference on Artificial Intelligence for Applications (CAIA '95). стр. 87-93, 1995.
У програмским језицима где су функције првокласни објекти (као што су Луа, Пајтон или Перл), аутоматска мемоизација се може имплементирати заменом (у фази извршења) функције са израчунатом вредношћу чим је вредност израчуната за задати скуп параметара. Функција која ради замену вредност–функцију–објекат може генерално да запакује сваку референцијално транспарентну функцију. Погледати следећи псеудокод (где је претпостављено да су функције прве класе):
function memoized-call (F is a function object parameter) if F has no attached array values then allocate an associative array called values; attach values to F; end if;
if F.values[arguments] is empty then F.values[arguments] = F(arguments); end if;
return F.values[arguments]; end function
Да бисмо позвали аутоматски мемоизвану верзију функције факторијел користећи ову стратегију, пре него директним позивом, псеудокод позива memoized-call(factorial(n)). Сваки такав позив прво проверава да ли је вектор вредности алоциран да ускладишти резултате и ако није, додаје вектор. Ако не постоје улази на позицији values[arguments] (где се arguments користе као кључ асоцијативног вектора), позива се функција факторијел са задатим аргументима. На крају, улаз у вектор на позицији кључа се враћа позиваоцу функције.
Горња стратегија захтева експлицитно паковање на сваки позив функције која треба да буде мемоизована. У језицима који омогућавају затварање, мемоизација може да се примени имплицитно помоћу функционалног објекта са функтором који враћа тај запаковани мемоизовани функционални објекат. У псеудокоду се то може написати на следећи начин:
function construct-memoized-functor (F is a function object parameter) allocate a function object called memoized-version;
let memoized-version(arguments) be if self has no attached array values then [self is a reference to this object] allocate an associative array called values; attach values to self; end if;
if self.values[arguments] is empty then self.values[arguments] = F(arguments); end if;
return self.values[arguments]; end let;
return memoized-version; end function
Уместо да се позове функција факторијел, се креира нови функционални објекат memfact на следећи начин: memfact = construct-memoized-functor(factorial) Горњи пример претпоставља да је функција факторијел већ дефинисана пре позива construct-memoized-functor. Од ове тачке па надаље memfact(n) се позива кад год је потребно израчунати факторијел од н. У језицима као што је Луа постоје софистицираније технике које омогућавају да функција буде замењена са новом функцијом са истим именом што дозвољава: factorial = construct-memoized-functor(factorial) У суштини, такве технике укључују додавање оригиналног функционалног објекта креираном функтору и прослеђивање позива оригиналној функцији која је мемоизована преко алијаса, када је потребан позив стварној функцији (да би се избегле бесконачне рекурзије) као што је приказано доле:
function construct-memoized-functor (F is a function object parameter) allocate a function object called memoized-version;
let memoized-version(arguments) be if self has no attached array values then [self is a reference to this object] allocate an associative array called values; attach values to self; allocate a new function object called alias; attach alias to self; [for later ability to invoke F indirectly] self.alias = F; end if;
if self.values[arguments] is empty then self.values[arguments] = self.alias(arguments); [not a direct call to F] end if;
return self.values[arguments]; end let;
return memoized-version; end function
(Примедба: неки од приказаних корака могу бити имплицитно одрађени у имплементираном језику и дати су ради илустрације.)
Парсери