Мемоизација

Мемоизација у рачунарству, је техника оптимизације која се најпре користи да би се убрзало извршавање рачунарских програма тако што се складиште резултати „скупих“ позива функција и враћају кеширани резултат када се поново јаве исти улази. Мемоизација се такође користи у другим контекстима (и за потребе које се не односе на убрзавање рачунарских програма), као што је у једноставној узајамној рекурзији опадајуће парсирање^[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 је инваријантан; ако се позива као 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 n^th 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

Да бисмо позвали аутоматски мемоизвану верзију функције факторијел користећи ову стратегију, пре него директним позивом, псеудокод позива 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

(Примедба: неки од приказаних корака могу бити имплицитно одрађени у имплементираном језику и дати су ради илустрације.)

Парсери

Када топ-даун парсер покушава да парсира неједнозначне улазе у односу на неједнозначну контекстно слободну граматику (CFG) може да му буде потребан експоненцијални број корака (у односу на дужину улаза) да би испитао све алтернативе CFG-а, да би произвео сва могућа стабла парцирања. То ће на крају захтевати експоненцијални меморијски простор. Мемоизација је испитана као стратегија парсирања 1991. године од стране Норвига, који је показао да алгоритам који је сличан коришћењу динамичког програмирања из скупова стања у Ерлијевом алгоритму (1970. године) и табелама у CYK алгоритму Кока Јунгера и Касамију може бити генерисан увођењем аутоматске мемоизације у једноставан повратни рекурзивни силазни парсер да би решио проблем експоненцијалне временске комплексности.^[1] Основна идеја у Норвиговом приступу је да када се парсер примени на улаз, резултат се ускладишти у мемо-табели за будућу употребу, ако се исти парсер поново користи на истом улазу. Ричард Фрост је такође користио мемоизацију да би смањио експоненцијалну временску комплексност парсерских комбинатора који може да се посматра као „чисто функционални топ-даун-бектрекинг“ парсинг техника.^[7] Он је показао да базични мемизовани парсер комбинатори могу да се користе за конструисање за изградњу комплетних парсера као извршна спецификација CFG-а.^[8]^[9] Ово се поново истраживали Џонсон and Dörre.^[10]^[11] и Дере у контексту парсирања 1995. године. 2002. године ово је детаљно истражио и Форд у форми названој пекрет-парсирање.^[12]

2007. године Фрост, Хафис и Калахан^[2] описали су топ-даун алгоритам за парсирање који користи мемоизацију да би умањили редундантна израчунавања и да би омогућили било који облик да би обезбедили извршење било ког облика неједнозначних CFG у полиномиалном времену (Θ(n⁴) за граматике са левом рекурзијом и Θ(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:

Правило А ће препознати xxxxxbd (тако што ће прво спуштање у X да би препознао један x и поновно спуштање у x док год сви мали x-ови нису препознати и после тога препознат b) и вратиће се на S и препустиће да препозна c. Следећи исказ S-а ће се спустити у B, што ће довести до поновног спуштања у X и препознаће x–еве помоћу више рекурзивних позива X и касније b и вратиће се у s и коначно препознати d.

Кључни концепт овде је инхерентан у фрази „поновно се спушта у X“. Процес предвиђања, промашаја, повратка и покушаја са следећом алтернативом се у парсирању зове бектрекинг и управо бектрекинг представља могућност за мемизацију у парсирању. Размотрите функцију RuleAcceptsSomeInput(Rule, Position, Input), где су следећи параметри:

Ruleје назив правила које се разматра.
Positionје офсет који тренутно разматрамо у оквиру улаза.
Inputје улаз који разматрамо.

Нека повратна вредност функције RuleAcceptsSomeInput буде дужина улаза прихваћеног од стране Rule или 0 ако то правило не прихвата ни један улаз на задатом офсету у низу. У бектрекинг сценарију са мемоизацијом, процес парсирања је следећи:

Када се правило А спусти на X на офсету 0, меморисаће се дужина 5 и правило X. После промашаја на d, B тада пре него што се спустимо поново на X да упитамо позицију 0 у односу на правило X у мемоизационој машини се враћа дужина од 5 тако да се штеди поновни силазак у X и то се понавља.

У горњем примеру једно или више спустања у X могу да се десе нпр. за низ као што су xxxxxxxxxxxxxxxxbd. У ствари, може да буде било који број x испред b. Док позив S мора рекурзивно да се спушта у X колико год има x, B никада неће морати да се спусти у X пошто је излазна вредност функције RuleAcceptsSomeInput(X, 0, xxxxxxxxxxxxxxxxbd) у овом случају 16.

Парсери који користе синтаксне предикате су такође у могућности да мемоизују резултате парсирања предиката и на тај начин редукују конструкције као што су:

 S → (A)? A
 A → /* some rule */

на једно спуштање у A.

Ако парсер направи стабло за време парсирања, он мора да мемоизује, не само дужину улаза која одговара неком офсету у односу на задато правило, него такође мора да складишти подстабло које је генерисано тим правилом на том офсету у улазу, пошто се наредни позиви правила неће у ствари спустити и обновити то стабло. Из истог разлога мемоизовани алгоритми парсирања који генеришу позиве екстерног кода (понекад се називају семантичке акционе рутине) када је правило ускладиштено, мора да постоји неки план који ће обезбедити да се таква правила позивају по предвидљивом редоследу.

Пошто, за било који задати парсер са бектрекингом или синтаксним предикатом неће свака граматика имати потребу за бектрекингом или провером предиката, допунски трошкови складиштења резултата парсирања сваког правила, сваки офсет у улазу (и складиштење стабла парсирања ако процес парсирања то ради имплицитно) може да успори парсер. Овај ефекат може да буде ублажен експлицитном селекцијом правила које ће парсер мемоизовати.^[14]

Види још

Теорија комплексности – више информација о комплексности алгоритама
Лукап табела – кључ структуре података који се користи у мемоизацији
Динамичко програмирање – неке апликације које користе технику мемоизације

Референце

^ ^а ^б ^в Norvig, Peter, "Techniques for Automatic Memoization with Applications to Context-Free Parsing," Computational Linguistics, Vol. 17 No. 1. стр. 91–98, March 1991.
^ ^а ^б Frost, Richard, Hafiz, Rahmatullah, and Callaghan, Paul. " Modular and Efficient Top-Down Parsing for Ambiguous Left-Recursive Grammars." 10th International Workshop on Parsing Technologies (IWPT), ACL-SIGPARSE , Pages: 109 – 120, June 2007, Prague.
^ ^а ^б Frost, Richard, Hafiz, Rahmatullah, and Callaghan, Paul. " Parser Combinators for Ambiguous Left-Recursive Grammars." 10th International Symposium on Practical Aspects of Declarative Languages (PADL), ACM-SIGPLAN , Volume 4902/2008, Pages: 167–181, January 2008, San Francisco.
^ Warren, David. "Tabling and Datalog Programming". Accessed 29 May 2009.
^ Hoffman, Berthold, "Term Rewriting with Sharing and Memoïzation," Algebraic and Logic Programming: Third International Conference, Proceedings, H. Kirchner and G. Levi (eds.). стр. 128–142, Volterra, Italy, 2–4 September 1992.
^ 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.
^ Frost, Richard. and Szydlowski, Barbara. "Memoizing Purely Functional Top-Down Backtracking Language Processors. " "Sci. Comput. Program. " 1996 – 27(3): 263–288.
^ Frost, Richard. "Using Memoization to Achieve Polynomial Complexity of Purely Functional Executable Specifications of Non-Deterministic Top-Down Parsers. " "SIGPLAN Notices" 29(4): 23–30.
^ Frost, Richard. "Monadic Memoization towards Correctness-Preserving Reduction of Search. " "Canadian Conference on AI 2003." p 66-80.
^ Johnson, Mark, "Memoization of Top-Down Parsing,” Computational Linguistics, Vol. 21 No. 3. стр. 405–417, September 1995.
^ ^а ^б Johnson, Mark & Dörre, Jochen, "Memoization of Coroutined Constraints," Proceedings of the 33rd Annual Meeting of the Association for Computational Linguistics, Cambridge, Massachusetts, 1995.
^ ^а ^б Ford, Bryan, Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking, Master’s thesis, Massachusetts Institute of Technology, September, 2002.
^ Tomita, Masaru. “Efficient Parsing for Natural Language.” Kluwer, Boston, MA, 1985.
^ Acar, Umut A. A. et al., "Selective Memoization," Proceedings of the 30th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, New Orleans, Louisiana. стр. 14–25, 15–17 January 2003.

Спољашње везе

Примери мемоизације у различитим програмским језицима

groovy.lang.Closure#memoize()
Memoize
IncPy Архивирано на сајту Wayback Machine (4. март 2016)
Dave Herman's Macros for defining memoized procedures
Memoize.pm
Java memoization
C++Memo^{[мртва веза]}
C-Memo
Tek271 Memoizer Архивирано на сајту Wayback Machine (8. мај 2019)
memoizable
Python memoization
OCaml memoization
Memoization in Lua
Memoization in Mathematica
Memoization in Javascript
Memoization in Javascript
X-SAIGA
Memoization in Scheme Архивирано на сајту Wayback Machine (14. јун 2010)
Memoization in Combinatory Logic.
MbCache

[Norvig1991-1] а ^б ^в Norvig, Peter, "Techniques for Automatic Memoization with Applications to Context-Free Parsing," Computational Linguistics, Vol. 17 No. 1. стр. 91–98, March 1991.

[FrostHafizCallaghan2007-2] а ^б Frost, Richard, Hafiz, Rahmatullah, and Callaghan, Paul. " Modular and Efficient Top-Down Parsing for Ambiguous Left-Recursive Grammars." 10th International Workshop on Parsing Technologies (IWPT), ACL-SIGPARSE , Pages: 109 – 120, June 2007, Prague.

[FrostHafizCallaghan2008-3] а ^б Frost, Richard, Hafiz, Rahmatullah, and Callaghan, Paul. " Parser Combinators for Ambiguous Left-Recursive Grammars." 10th International Symposium on Practical Aspects of Declarative Languages (PADL), ACM-SIGPLAN , Volume 4902/2008, Pages: 167–181, January 2008, San Francisco.

[Warren1999-4] Warren, David. "Tabling and Datalog Programming". Accessed 29 May 2009.

[Hoffman1992-5] Hoffman, Berthold, "Term Rewriting with Sharing and Memoïzation," Algebraic and Logic Programming: Third International Conference, Proceedings, H. Kirchner and G. Levi (eds.). стр. 128–142, Volterra, Italy, 2–4 September 1992.

[MayfieldEtAl1995-6] 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.

[Frost1996-7] Frost, Richard. and Szydlowski, Barbara. "Memoizing Purely Functional Top-Down Backtracking Language Processors. " "Sci. Comput. Program. " 1996 – 27(3): 263–288.

[Frost1994-8] Frost, Richard. "Using Memoization to Achieve Polynomial Complexity of Purely Functional Executable Specifications of Non-Deterministic Top-Down Parsers. " "SIGPLAN Notices" 29(4): 23–30.

[Frost2003-9] Frost, Richard. "Monadic Memoization towards Correctness-Preserving Reduction of Search. " "Canadian Conference on AI 2003." p 66-80.

[Johnson1995-10] Johnson, Mark, "Memoization of Top-Down Parsing,” Computational Linguistics, Vol. 21 No. 3. стр. 405–417, September 1995.

[Johnson&Dorre-11] а ^б Johnson, Mark & Dörre, Jochen, "Memoization of Coroutined Constraints," Proceedings of the 33rd Annual Meeting of the Association for Computational Linguistics, Cambridge, Massachusetts, 1995.

[Ford2002-12] а ^б Ford, Bryan, Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking, Master’s thesis, Massachusetts Institute of Technology, September, 2002.

[Tomita1985-13] Tomita, Masaru. “Efficient Parsing for Natural Language.” Kluwer, Boston, MA, 1985.

[AcarEtAl2003-14] Acar, Umut A. A. et al., "Selective Memoization," Proceedings of the 30th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, New Orleans, Louisiana. стр. 14–25, 15–17 January 2003.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]