Бағдарламалық қамтамасыз етуді оңтайландыру: Жадыда сақтау әдісі

Кіріспе

Бағдарламалық жасақтаманы бағдарламалауды оңтайландыру тәсілі

Есептеу техникасында, мемоизация – компьютерлік бағдарламаларды жылдамдету үшін негізгі арналған оптимизациялау тәсілі. Бұл тәсіл қымбат функция шақыруларының нәтижелерін сақтап, сол функция таза болса, бірдей кіріс мәліметтері кезінде сақталған нәтижені қайтару арқылы жұмыс істейді. Мемоизация жылдамдық артудан басқа мақсаттар үшін де, мысалы, қарапайым өзара рекурсивті түсіп келу синтаксистік талдауында қолданылған. Бұл кэштеудің бір түрі, буферлеу және бет алмастыру сияқты басқа кэштеу түрлерінен ерекшеленеді. Кейбір логикалық бағдарламалау тілдерінде мемоизация кестелеу деп те аталады.

Этимология

Мемоизация термині 1968 жылы Дональд Мичимен енгізілген. Ол латынша memorandum сөзінен туындаған ("есте сақтауға арналған"), американдық ағылшын тілінде көбінесе memo деп қысқартылады, демек, "функцияның нәтижесін есте сақтауға айналдыру" мағынасын білдіреді. Мемоизациялау мен жаттау ұғымдары шатастырылуы мүмкін (олар этимологиялық жақтан байланысты болғандықтан), бірақ мемоизациялау есептеу саласында нақты мағынаға ие.

Функционалдық бағдарламалау

Мемоизация функционалдық бағдарламалау тілдерінің компиляторларында кеңінен қолданылады, олар көбінесе аргументтерді атау бойынша бағалау стратегиясын пайдаланады. Аргумент мәндерін есептеуге байланысты қосымша шығындарды болдырмау үшін, осы тілдердің компиляторлары аргумент мәндерін есептеу үшін thunk деп аталатын қосымша функцияларды жиі пайдаланады және осы функцияларды қайта есептеуден аулақ болу үшін жадта сақтайды.

Талдаушылар

Жоғарыдан төменге қарай талдаушы екіжақты контекстсіз грамматикаға (CFG) қатысты екіжақты кірісті талдауды бастағанда, CFG-нің барлық баламаларын сынап көру үшін барлық мүмкін талдау ағаштарын жасау үшін қадамдардың экспоненциалдық саны (кірістің ұзындығына қатысты) қажет болуы мүмкін. Бұл үшін экспоненциалды жад кеңістігі қажет. Мемоизацияны 1991 жылы Питер Норвиг талдау стратегиясы ретінде зерттеді. Ол Эрли алгоритміне (1970) динамикалық бағдарламалау мен күй жиынтықтарын пайдалануға ұқсас алгоритмнің және Кокке, Янгер және Касамидің CYK алгоритміндегі кестелердің экспоненциалдық уақыт күрделілігі проблемасын шешу үшін қарапайым кері рекурсивті түсіру талдаушысына автоматты мемоизацияны енгізу арқылы жасалуы мүмкін екенін көрсетті. Фрост негізгі мемоизацияланған талдау комбинаторларын CFG-ның орындалатын сипаттамалары ретінде күрделі талдауларды құру үшін құрылыс блоктары ретінде пайдалануға болатынын көрсетті. Мемоизацияны 1995 жылы Марк Джонсон мен Йохен Дёрре қайтадан талдау аясында зерттеді. 2002 жылы Брайан Форд оны Packrat parsing деп аталатын формада терең зерттеді. 2007 жылы Фрост, Хафиз және Каллаган жоғарыдан төменге қарай талдау алгоритмін сипаттады, ол артық есептеулерді болдырмау үшін мемоизацияны қолданады, соның арқасында кез келген екіжақты CFG түрін көп уақытта (сол рекурсивті грамматикалар үшін Θ(n4) және сол рекурсивті емес грамматикалар үшін Θ(n3)) орналастыруға болады. Олардың жоғарыдан төменге қарай талдау алгоритмі "жинақы бейнелеу" және "жергілікті түсініксіздіктерді топтастыру" арқылы потенциалды экспоненциалды екіжақты талдау ағаштары үшін көп мөлшерде жадты қажет етеді. Олардың жинақы бейнелеуі Томитаның төменнен жоғары қарай талдаудың жинақы бейнелеуімен салыстыруға болады. Олардың мемоизацияны пайдалануы тек бір кіріс позициясына бірнеше рет талдаушы қолданылған кезде бұрын есептелген нәтижелерді алумен ғана шектелмейді (бұл көп уақытты талап ету үшін маңызды); ол келесі қосымша тапсырмаларды орындау үшін мамандандырылған: Мемоизация процесі (бұл кез-келген талдаушыны орындаудың айналасындағы "wrapper" ретінде қаралуы мүмкін) кіріс ұзындығы мен ағымдағы кіріс позициясына қатысты тереңдік шектеулерін енгізе отырып, үнемі өсіп келе жатқан тікелей сол рекурсивті талдауды қамтиды. Алгоритмнің меморандумдық кестесінің "іздеу" процедурасы сонымен қатар сақталған нәтиженің есептеу контекстін талдаушының ағымдағы контексімен салыстыру арқылы сақталған нәтиженің қайта пайдалануға қабілеттілігін анықтайды. Бұл контексттік салыстыру - жанама (немесе жасырын) сол жақ рекурсияны орналастырудың кілті. Мемотабельді сәтті іздеуді орындаған кезде, толық нәтиже жиынтығын қайтарудың орнына, процесс тек нақты нәтижеге сілтемелерді қайтарады және ақыр соңында жалпы есептеуді жылдамдатады. Мемотабельді жаңарту кезінде мемоизация процесі (потенциалды экспоненциалды) екіжақты нәтижелерді топтастырады және көп мөлшерде жадты талап етуді қамтамасыз етеді. Фрост, Хафиз және Каллаган PADL08-де алгоритмнің жүзеге асырылуын Haskell-те жоғары реттік функциялар жиынтығы (парсерлік комбинаторлар деп аталады) ретінде сипаттады, бұл CFG-ның тікелей орындалатын сипаттамаларын тіл процессорлары ретінде құруға мүмкіндік береді. Олардың көп уақыттық алгоритмінің "жоғарыдан төменге қарай талдаумен" "кез келген екіжақты CFG" түрін орналастыруға қабілеттілігінің маңызы табиғи тіл өңдеу кезінде синтаксис пен семантика талдауына қатысты өте маңызды. X SAIGA сайтында алгоритм мен іске асыру туралы егжей-тегжейлі ақпарат бар. Норвиг талдаушының қуатын мемоизация арқылы арттырғанмен, кеңейтілген талдаушы әлі де Эрли алгоритмі сияқты уақыт жағынан күрделі болды, бұл жылдамдықты оңтайландырудан басқа нәрсе үшін мемоизацияны қолдану жағдайын көрсетеді. Джонсон мен Дёрре.

When a top down parser tries to parse an ambiguous input with respect to an ambiguous context free grammar (CFG), it may need an exponential number of steps (with respect to the length of the input) to try all alternatives of the CFG in order to produce all possible parse trees. This eventually would require exponential memory space. Memoization was explored as a parsing strategy in 1991 by Peter Norvig, who demonstrated that an algorithm similar to the use of dynamic programming and state sets in Earley's algorithm (1970), and tables in the CYK algorithm of Cocke, Younger and Kasami, could be generated by introducing automatic memoization to a simple backtracking recursive descent parser to solve the problem of exponential time complexity. Frost showed that basic memoized parser combinators can be used as building blocks to construct complex parsers as executable specifications of CFGs. Memoization was again explored in the context of parsing in 1995 by Mark Johnson and Jochen Dörre. In 2002, it was examined in considerable depth by Bryan Ford in the form called packrat parsing. In 2007, Frost, Hafiz and Callaghan described a top down parsing algorithm that uses memoization for refraining redundant computations to accommodate any form of ambiguous CFG in polynomial time (Θ(n4) for left recursive grammars and Θ(n3) for non left recursive grammars). Their top down parsing algorithm also requires polynomial space for potentially exponential ambiguous parse trees by 'compact representation' and 'local ambiguities grouping'. Their compact representation is comparable with Tomita's compact representation of bottom up parsing. Their use of memoization is not only limited to retrieving the previously computed results when a parser is applied to a same input position repeatedly (which is essential for polynomial time requirement); it is specialized to perform the following additional tasks:
The memoization process (which could be viewed as a ‘wrapper’ around any parser execution) accommodates an ever growing direct left recursive parse by imposing depth restrictions with respect to input length and current input position. The algorithm's memo table ‘lookup’ procedure also determines the reusability of a saved result by comparing the saved result's computational context with the parser's current context. This contextual comparison is the key to accommodate indirect (or hidden) left recursion. When performing a successful lookup in a memotable, instead of returning the complete result set, the process only returns the references of the actual result and eventually speeds up the overall computation. During updating the memotable, the memoization process groups the (potentially exponential) ambiguous results and ensures the polynomial space requirement. Frost, Hafiz and Callaghan also described the implementation of the algorithm in PADL’08 as a set of higher order functions (called parser combinators) in Haskell, which enables the construction of directly executable specifications of CFGs as language processors. The importance of their polynomial algorithm's power to accommodate ‘any form of ambiguous CFG’ with top down parsing is vital with respect to the syntax and semantics analysis during natural language processing. The X SAIGA site has more about the algorithm and implementation details. While Norvig increased the power of the parser through memoization, the augmented parser was still as time complex as Earley's algorithm, which demonstrates a case of the use of memoization for something other than speed optimization. Johnson and Dörre