МемоизацијаМемоизација у рачунарству, је техника оптимизације која се најпре користи да би се убрзало извршавање рачунарских програма тако што се складиште резултати „скупих“ позива функција и враћају кеширани резултат када се поново јаве исти улази. Мемоизација се такође користи у другим контекстима (и за потребе које се не односе на убрзавање рачунарских програма), као што је у једноставној узајамној рекурзији опадајуће парсирање[1] у општем топ-даун (одозго-надоле) алгоритму[2][3] за парсирање, који прилагођава двосмисленост и леву рекурзију у полиномиалном времену и простору. Иако је везана за кеширање, мемоизација указује на специфичан случај ове оптимизације, разликовајући је од облика кеширања као што су баферовање или замена страница. У контексту неких логичких програмских језика, мемоизација је такође позната као табелирање;[4] погледати такође лукап табеле. ЕтимологијаТермин „мемоизација“ је увео Доналд Мичи (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 укључује кумулативне трошкове корака 2 до 6, који су пропорционални иницијалној вредности n. Мемоизована верзија функције 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! је већ складиштена од претходног позива. На тај начин мемоизација омогућава да функција постане ефикаснија у времену извршења, што се више позива. То коначно доприноси општем убрзању извршења функције. Остала разматрањаФункционално програмирањеМемоизација се много користи у компајлерима за функционалне програмске језике, који често користе стратегију еваулације позива по имену. Да би избегли допунске трошкове везане за израчунавање вредности аргумената, компајлери за ове језике често користе помоћне функције које се зову танкови (претварачи) да би израчунали вредности аргумента и мемоизовали ове функције да би се избегло поновно израчунавање. Аутоматска мемоизацијаДок мемоизација може да буде придружена функцијама интерно и експлицитно од стране програмера, на исти такав начин горе поменута мемоизована функција факторијел може да буде аутоматски мемоизована екстерно[1]. Технике које је користио Петер Норвиг (Peter Norvig) имају примену, не само у Лиспу (језик у коме је представио аутоматску мемизацију), него и у другим програмским језицима. Примена аутоматске мемоизације су формално истражене и у студијама преписивања термина[5] и вештачкој интелигенцији.[6] У програмским језицима где су функције првокласни објекти (као што су Луа, Пајтон или Перл[1]), аутоматска мемоизација се може имплементирати заменом (у фази извршења) функције са израчунатом вредношћу чим је вредност израчуната за задати скуп параметара. Функција која ради замену вредност–функцију–објекат може генерално да запакује сваку референцијално транспарентну функцију. Погледати следећи псеудокод (где је претпостављено да су функције прве класе): 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
Да бисмо позвали аутоматски мемоизвану верзију функције факторијел користећи ову стратегију, пре него директним позивом, псеудокод позива Горња стратегија захтева експлицитно паковање на сваки позив функције која треба да буде мемоизована. У језицима који омогућавају затварање, мемоизација може да се примени имплицитно помоћу функционалног објекта са функтором који враћа тај запаковани мемоизовани функционални објекат. У псеудокоду се то може написати на следећи начин: 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) Горњи пример претпоставља да је функција факторијел већ дефинисана пре позива 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
(Примедба: неки од приказаних корака могу бити имплицитно одрађени у имплементираном језику и дати су ради илустрације.) ПарсериКада топ-даун парсер покушава да парсира неједнозначне улазе у односу на неједнозначну контекстно слободну граматику (CFG) може да му буде потребан експоненцијални број корака (у односу на дужину улаза) да би испитао све алтернативе CFG-а, да би произвео сва могућа стабла парцирања. То ће на крају захтевати експоненцијални меморијски простор. Мемоизација је испитана као стратегија парсирања 1991. године од стране Норвига, који је показао да алгоритам који је сличан коришћењу динамичког програмирања из скупова стања у Ерлијевом алгоритму (1970. године) и табелама у CYK алгоритму Кока Јунгера и Касамију може бити генерисан увођењем аутоматске мемоизације у једноставан повратни рекурзивни силазни парсер да би решио проблем експоненцијалне временске комплексности.[1] Основна идеја у Норвиговом приступу је да када се парсер примени на улаз, резултат се ускладишти у мемо-табели за будућу употребу, ако се исти парсер поново користи на истом улазу. Ричард Фрост је такође користио мемоизацију да би смањио експоненцијалну временску комплексност парсерских комбинатора који може да се посматра као „чисто функционални топ-даун-бектрекинг“ парсинг техника.[7] Он је показао да базични мемизовани парсер комбинатори могу да се користе за конструисање за изградњу комплетних парсера као извршна спецификација CFG-а.[8][9] Ово се поново истраживали Џонсон and Dörre.[10][11] и Дере у контексту парсирања 1995. године. 2002. године ово је детаљно истражио и Форд у форми названој пекрет-парсирање.[12] 2007. године Фрост, Хафис и Калахан[2] описали су топ-даун алгоритам за парсирање који користи мемоизацију да би умањили редундантна израчунавања и да би омогућили било који облик да би обезбедили извршење било ког облика неједнозначних CFG у полиномиалном времену (Θ(n4) за граматике са левом рекурзијом и Θ(n³) за граматике са нелевом рекурзијом). Њихов топ-даун алгоритам за парцирање такође захтева полиномиални простор за потенцијално експоненцијална неједнозначна стабла парсирања помоћу „компкатног предстаљања“ и „локално групирање неједнозначности“. Њихово компактно представљање је упоредиво са компактним представљањем у Томитином ботом-уп[13] парсингу. Њихово коришћење мемоизације није само ограничено на повраћај претходно израчунатих резултата када се парсер употребљава на истим улазним вредностима више пута (што је суштински важно за захтев за полиномиалним временом); оно је специјализовано и за следеће допунске задатке:
Фрост, Хафис и Калахан су такође описали имплементацију алгоритма у PADL’08[3] као скуп функција вишег реда (звани парсер кобминатори) у Хаскел-у, који омогућава директно извршне спецификације CFG као процесора језика. Значај снаге њиховог полиномиалног алгоритма да укључи „било који облик“ једнозначног CFG са топ-даун парсирањем је витална за синтаксну и семантичку анализу приликом обраде природних језика. На X-SAIGA сајту може се сазнати више о детаљима алгоритма и имплементације. Док је Норвиг повећао снагу парсера помоћу мемоизације, унапређени парсер је и даље био временски комплексан као и Ерлијев алгоритам који приказује случај коришћења мемоизације за нешто друго него што је мемоизација брзине. Џонсон и Дере[11] приказују другу такву примену мемоизације која се не односи на брзину: коришћење мемоизације да би се одложила резолуција лингвистичких ограничења до тачке у процесу парсирања где су акумулиране довољне информације, да би се та ограничења разрешила. Насупрот томе, у примени мемоизације за оптимизацију брзине, Форд је приказао да мемоизација може да гарантује да граматике за парсирање израза могу да се изврше у линеарно времену, чак и код језика који имају најгоре бектрекинг-понашање.[12] Размотрите следећу граматику: S → (A c) | (B d) A → X (a|b) B → X b X → x [X] Ова граматика генерише једну од следеће три варијације низова: xac, xbc, или xbd (где се за x подразумева један или више x-ова). Следеће размотрите како ова граматика коришћена као спецификација за парсирање може да утиче на топ-даун, лево-десно парсирање низа xxxxxbd:
Кључни концепт овде је инхерентан у фрази „поновно се спушта у X“. Процес предвиђања, промашаја, повратка и покушаја са следећом алтернативом се у парсирању зове бектрекинг и управо бектрекинг представља могућност за мемизацију у парсирању. Размотрите функцију
Нека повратна вредност функције
У горњем примеру једно или више спустања у X могу да се десе нпр. за низ као што су xxxxxxxxxxxxxxxxbd. У ствари, може да буде било који број x испред b. Док позив S мора рекурзивно да се спушта у X колико год има x, B никада неће морати да се спусти у X пошто је излазна вредност функције Парсери који користе синтаксне предикате су такође у могућности да мемоизују резултате парсирања предиката и на тај начин редукују конструкције као што су:
S → (A)? A A → /* some rule */ на једно спуштање у A. Ако парсер направи стабло за време парсирања, он мора да мемоизује, не само дужину улаза која одговара неком офсету у односу на задато правило, него такође мора да складишти подстабло које је генерисано тим правилом на том офсету у улазу, пошто се наредни позиви правила неће у ствари спустити и обновити то стабло. Из истог разлога мемоизовани алгоритми парсирања који генеришу позиве екстерног кода (понекад се називају семантичке акционе рутине) када је правило ускладиштено, мора да постоји неки план који ће обезбедити да се таква правила позивају по предвидљивом редоследу. Пошто, за било који задати парсер са бектрекингом или синтаксним предикатом неће свака граматика имати потребу за бектрекингом или провером предиката, допунски трошкови складиштења резултата парсирања сваког правила, сваки офсет у улазу (и складиштење стабла парсирања ако процес парсирања то ради имплицитно) може да успори парсер. Овај ефекат може да буде ублажен експлицитном селекцијом правила које ће парсер мемоизовати.[14] Види још
Референце
Спољашње везе
|
Portal di Ensiklopedia Dunia
