Мемоїзація
Мемоїзація — це метод оптимізації, який в основному використовується для прискорення комп'ютерних програм шляхом зберігання результатів дорогих викликів функцій та повернення кешованого результату, коли виклики на однакових вхідних даних відбуваються знову. Мемоізація також використовується в інших контекстах (та для цілей, відмінних від прискорення швидкості), наприклад, у простому взаємному рекурсивному спуску[1]. Хоча мемоізація пов'язана з кешуванням, вона відноситься до конкретного випадку цієї оптимізації, яка відрізняє її від інших форм кешування, таких як буферизація або заміщення сторінок. У контексті деяких мов логічного програмування мемоізація також відома як табулювання[2]; див. також таблицю пошуку.
Термін «мемоізація» був придуманий Дональдом Мічі[en] в 1968 році[3] та походить від латинського слова «memorandum» («пам'ятати»), яке зазвичай скорочують як «memo» в американській англійській мові, і таким чином несе сенс «перетворення результатів функції на щось, що слід пам'ятати».
Мемоізована функція «запам'ятовує» результати, що відповідають деякому набору конкретних вхідних даних. Наступні виклики з запам'ятованими вхідними даними повертають запам'ятований результат, а не обчислюють його наново, тим самим усувається початкова вартість усіх викликів функції з заданими параметрами, окрім самого першого виклику. Множина таких зв'язків, що запам'ятовуються, може бути фіксованих розмірів, та керуватись алгоритмом, який виконує оновлення, або може бути фіксованою множиною, залежною від природи функції та її використання. Функція може бути мемоізована, якщо вона прозора по посиланнях; тобто, лише якщо виклик функції має точно такий же ефект, як і заміна виклику функції величиною, що повертається. (Однак існують особливі винятки для цього обмеження.) Оскільки мемоізація часто використовує у своїй реалізації таблиці пошуку, мемоізація заповнює свій кеш результатів прозоро на льоту, за потреби, а не заздалегідь.
Мемоізація — це спосіб знизити часові витрати функції в обмін на вартість простору; мемоізовані функції оптимізують швидкість шляхом використання пам'яті комп'ютера. Часова/просторова «вартість» алгоритмів має спеціальну назву в обчислювальній техніці: обчислювальна складність. Всі функції мають обчислювальну складність в часі (тобто, вони потребують часу для виконання) і в просторі.
Хоча відбувається просторово-часова домовленість (тобто, використаний простір збільшує швидкість), це відрізняється від деяких інших оптимізацій, які включають просторово-часову домовленість, таких, як зниження вартості операцій[en], в якій мемоізація є оптимізацією часу виконання[en], а не компіляції[en]. Крім того, зниження вартості операцій потенційно замінює дорогі операції, таку як множення, менш витратною операцією додавання, та результати економії можуть бути залежними від машин, тоді як мемоізація є багатоплатформною стратегією, яка не залежить від машин.
Розглянемо наступний псевдокод функції, яка обчислює факторіал:
функція факторіал (n — невід'ємне ціле число)
якщо n = 0 тоді
повернути 1 [за конвенцією 0! = 1]
інакше
повернути факторіал(n – 1) помножений на n [рекурсивно викликаємо факторіал з параметром n меншим на 1]
Для кожного цілого числа n такого, що n ≥ 0, кінцевий результат функції факторіал є інваріантним; у результаті виклику x = факторіал(3) змінна x завжди буде мати значення 6. Немемоізована реалізація, наведена вище, з урахуванням природи рекурсивного алгоритму, вимагатиме n + 1 викликів факторіалу для отримання результату, і кожен з цих викликів, у свою чергу, має пов'язану вартість часу виконання. Залежно від машини ця вартість може бути сумою:
- Вартість встановлення фрейму стека функціональних викликів.
- Вартість порівняння n з 0.
- Вартість віднімання 1 від n.
- Вартість встановлення рекурсивного фрейму стека функціональних викликів. (Як і вище.)
- Вартість множення результату рекурсивного виклику функції
факторіална n. - Вартість зберігання повернутого результату для його використання контекстом виклику.
У немемоізованій реалізації кожен виклик верхнього рівня функції факторіал включає сукупну вартість кроків 2—6, пропорційну початковому значенню n.
Мемоізована функція факторіал:
функція факторіал (n — невід'ємне ціле число)
якщо n = 0 тоді
повернути 1 [за конвенцією 0! = 1]
інакше якщо n у таблиці-пошуку тоді
повернути значення-n-у-таблиці-пошуку
інакше
нехай x = факторіал(n – 1) помножений на n [рекурсивно викликаємо факторіал з параметром n меншим на 1]
зберегти x у таблиці-пошуку у n-ому слоті [запам'ятовуємо результат n! на майбутнє]
повернути x
У цьому конкретному прикладі, якщо факторіал спочатку викликається з 5, то результат запам'ятається для будь-якого значення, меншого або рівного 5, оскільки факторіал буде викликаний рекурсивно зі значеннями 5, 4, 3, 2, 1 та 0, і повернуті значення для кожного з викликів будуть збережені (окрім 0, так як це базовий випадок). Якщо він викликається з числом, що перевищує 5, наприклад, 7, буде зроблено тільки 2 рекурсивних виклику (7 і 6), а значення для 5! буде збережено з попереднього виклику. Таким чином, чим частіше викликається функція, тим більшого ефекту надає мемоізація, що призводить до загального прискорення програми.
Мемоізація значною мірою використовується в компіляторах для функційних мов програмування, які часто використовують стратегію виклику по імені. Щоб уникнути накладних витрат при обчисленні значень аргументів, компілятори для цих мов використовують додаткові функції, що називаються thunks, для обчислення значень аргументів і мемоізації результатів функцій.
Хоча мемоізація може бути додана до функцій внутрішньо і явно комп'ютерним програмістом майже так само, як реалізована вищезазначена функція факторіал, прозорі по посиланнях функції також можуть бути автоматично мемоізовані зовні.[1] Методи, застосовані Пітером Норвігом, використовуються не тільки в Common Lisp (мова, на якій його робота демонструвала автоматичну мемоізацію), але й в інших мовах програмування. Застосування автоматичної мемоізації також було формально вивчене при дослідженні рерайтингу термів[4] та штучного інтелекту.[5]
У мовах програмування, де функції є об'єктами першого класу (такі як Lua, Python та Perl [1] [Архівовано 16 серпня 2019 у Wayback Machine.]), автоматична мемоізація може бути реалізована шляхом заміни (під час виконання[en]) функції на її обчислене значення після того, як було обчислено значення для даного набору параметрів. Функція, що виконує цю заміну, може обгортати будь-яку прозору по посиланнях функцію. Розглянемо наступний псевдокод (який передбачає, що функції є об'єктами першого класу):
функція мемоізований-виклик (F — об'єкт функції)
якщо F не має приєднаного масиву з назвою значення тоді
виділити асоціативний масив з назвою значення
приєднати значення до F
якщо F.значення[аргументи] порожнє тоді
F.значення[аргументи] = F(аргументи)
повернути F.значення[аргументи]
Для того, щоб викликати автоматично мемоізовану версію функції факторіал, використовуючи вищезазначену стратегію, замість того, щоб викликати факторіал безпосередньо, код викликає мемоізований-виклик(факторіал(n)). Кожний такий виклик спочатку перевіряє, чи був виділений масив для зберігання результатів, а якщо ні, приєднує цей масив. Якщо не існує запису в позиції значення[аргументи] (де аргументи використовуються як ключ асоціативного масиву), то робиться справжній виклик функції факторіал з наведеними аргументами. Нарешті, запис в масиві на позиції ключа повертається викликаючому.
Вищезазначена стратегія вимагає явного обгортання при кожному виклику функції, яка має бути мемоізована. У мовах, які підтримують замикання, мемоізація може бути здійснена неявно фабрикою функторів, яка повертає обгорнутий мемоізований об'єкт функції. У псевдокоді це може бути виражено наступним чином:
функція побудувати-мемоізований-функтор (F — об'єкт функції)
виділити об'єкт функції мемоізована-версія
нехай мемоізована-версія(аргументи) є
якщо this не має приєднаного масиву значень тоді
виділити асоціативний масив з назвою значення
приєднати значення до this
якщо this.значення[аргументи] порожнє тоді
this.значення[аргументи] = F(аргументи)
повернути this.значення[аргументи]
повернути мемоізована-версія
Замість використання функції факторіал, створюється новий об'єкт функції мемоізований-факторіал наступним чином:
мемоізований-факторіал = побудувати-мемоізований-функтор(факторіал)
Наведений вище приклад передбачає, що функція факторіал вже визначена до того, як буде зроблено виклик побудувати-мемоізований-функтор. Надалі потрібно викликати функцію мемоізований-факторіал замість факторіал, коли необхідно обчислити n!. У таких мовах, як Lua, існують більш витончені методи, які дозволяють замінити функцію новою функцією з тим же ім'ям:
факторіал = побудувати-мемоізований-функтор(факторіал)
По суті, такі методи включають в себе приєднання оригінального об'єкта функції до створеного функтора і переадресацію викликів до оригінальної функції через синонім у випадках, коли необхідний виклик оригінальної функції (щоб уникнути нескінченної рекурсії), як показано нижче:
функція побудувати-мемоізований-функтор (F — об'єкт функції)
виділити об'єкт функції мемоізована-версія
нехай мемоізована-версія(аргументи) є
якщо this не має приєднаного масиву значень тоді
виділити асоціативний масив з назвою значення
приєднати значення до this
виділити новий об'єкт функції синонім
приєднати синонім до this
this.синонім = F
якщо this.значення[аргументи] порожнє тоді
this.значення[аргументи] = this.alias(arguments); [не є прямим викликом F]
повернути this.значення[аргументи]
повернути мемоізована-версія
Примітка: деякі з описаних вище кроків можуть бути неявно керовані мовою реалізації та надані для ілюстрації.
Під час низхідного синтаксичного аналізу, коли парсер намагається розібрати неоднозначний вхід щодо неоднозначної контекстно-вільної граматики (КВ граматика), може знадобитися експонентне число кроків (щодо довжини вхідного сигналу), щоб спробувати всі альтернативи КВ граматики для того, щоб створити всі можливі дерева розбору. Зрештою це потребує експоненційного простору пам'яті. У 1991 році Пітер Норвіг використав мемоізацію як стратегію синтаксичного аналізу. Він продемонстрував, що алгоритм аналогічний використанню динамічного програмування і множин станів в алгоритмі Ерлі (1970) та таблиці в алгоритмі Кока—Янгера—Касамі[en], можна було б генерувати шляхом введення автоматичної мемоізації до простого аналізатора зворотного рекурсивного спуску для вирішення проблеми експоненційної складності часу.[1] Основна ідея підходу Норвіга полягає в тому, що, коли парсер застосовується до входу, результат зберігається в пам'яті для подальшого повторного використання. Річард Фрост також використовував мемоізацію для зменшення експоненціальної часової складності комбінаторів парсерів[en].[6] Він показав, що основні базові комбінатори парсерів можуть бути використані як будівельні блоки для побудови складних парсерів.[7][8] Це було знову досліджено в контексті парсингу в 1995 році Джонсоном і Дорре.[9][10] У 2002 році мемоізація у контексті синтаксичного аналізу була глибоко вивчена Фордом.[11]
У 2007 році Фрост, Хафіз і Каллахан описали алгоритм низхідного аналізу, який використовує мемоізацію для утримання надмірних обчислень для розміщення будь-якої форми неоднозначної контекстно-вільної граматики за поліноміальний час (Θ(n⁴) для ліворекурсивних[en] та Θ(n³) для не ліворекурсивних граматик). Їх алгоритм низхідного аналізу також вимагає поліноміального простору для потенційно експоненціальних неоднозначних дерев розбору за допомогою «компактного представлення» і «групування місцевих неоднозначностей». Їх компактне представлення можна порівняти з компактним представленням Томіти висхідного аналізу[en].[12] Їхнє використання мемоізації не тільки обмежується вилученням раніше обчислених результатів, коли парсер повторно застосовується до однієї позиції входу (що є необхідним для вимоги поліноміального часу), воно спеціалізується на виконанні наступних додаткових завдань:
- Процес мемоізації (який можна розглядати як «обгортку» навколо виконання будь-якого парсера) пристосовує зростальний прямий ліворекурсивний аналіз, встановлюючи обмеження глибини щодо вхідної довжини і поточної позиції входу.
- Процедура алгоритму для пошуку у таблиці також визначає можливість повторного використання збереженого результату шляхом порівняння обчислювального контексту збереженого результату з поточним контекстом синтаксичного аналізатора. Це контекстне порівняння є ключем для пристосування непрямої (або прихованої) лівої рекурсії.
- При виконанні успішного пошуку в таблиці, замість того, щоб повертати повний набір результатів, процес повертає лише посилання на фактичний результат і зрештою прискорює швидкість обчислення.
- Під час оновлення таблиці мемоізації, процес мемоізації групує (потенційно експоненційні) неоднозначні результати і забезпечує вимогу поліноміального простору.
Фрост, Хафіз і Каллахан також описали реалізацію алгоритму в PADL'08 як набір функцій вищого порядку (які називаються комбінаторами парсерів[en]) в Haskell, що дозволяє будувати безпосередньо виконувані специфікації контекстно-вільних граматик як мовних процесорів. Потужність їх поліноміального алгоритму для розміщення «будь-якої форми неоднозначної КВ граматики» за допомогою низхідного синтаксичного аналізу є необхідною для аналізу синтаксису та семантики під час обробки природних мов. Сайт X-SAIGA [Архівовано 4 квітня 2013 у Wayback Machine.] має більше інформації про алгоритм і деталі його реалізації.
Хоча Норвіг збільшив потужність синтаксичного аналізатора через мемоізацію, розширений синтаксичний аналізатор все ще вимагав багато часу для виконання, як алгоритм Ерлі, що демонструє випадок використання мемоізації для цілей, відмінних від оптимізації швидкості. Джонсон і Дорре[10] продемонстрували ще одне таке застосування мемоізації: використання мемоізації для відкладання вирішення лінгвістичних обмежень до моменту в аналізі, де накопиченої інформації достатньо для вирішення цих обмежень. На відміну від цього, при застосуванні мемоізації для оптимізації швидкості, Форд продемонстрував, що мемоізація може гарантувати, що граматики розбіру виразів[en] можуть аналізувати за лінійний час навіть ті мови, які призвели до поведінки у найгіршому випадку.[11]
Розглянемо наступну граматику:
S → (A c) | (B d) A → X (a|b) B → X b X → x [X]
Ця граматика генерує одну з наступних трьох варіацій рядка: xac, xbc або xbd (де x тут розуміється як одне або більше x). Далі розглянемо, як ця граматика, яка використовується як специфікація розбору, може вплинути на розбір рядка xxxxxbd при низхідному аналізі:
- Правило A розпізнає xxxxxb (спочатку спускаючись у X, щоб розпізнати один x, і знову спускаючись у X, доки всі x не будуть розпізнані, а потім розпізнаючи b), а потім повертається до S, де не може розпізнати c. Наступний пункт S потім буде спускатися в B, який в свою чергу знову спускається в X і розпізнає х за допомогою багатьох рекурсивних викликів X, потім b, і повертається до S і нарешті розпізнає d.
Ключова концепція тут притаманна фразі «знову спускається в X». Цей процес пошуку називається пошуком з вертанням і саме він надає можливість використовувати мемоізацію у синтаксичному аналізі. Розглянемо функцію ПравилоПриймаєДеякіВходи(Правило, Позиція, Вхід) з такими параметрами:
Правило— назва розглянутого правила.Позиція— позиція у розглянутих вхідних даних.Вхід— розглянуті вхідні дані.
Нехай повернене значення функції ПравилоПриймаєДеякіВходи є довжиною вхідних даних, прийнятих Правилом, або 0, якщо це правило не приймає жодного вводу в цій позиції в рядку. У сценарії пошуку з вертанням з мемоізацією процес аналізу виглядає наступним чином:
- Коли правило А спускається в X на позиції 0, воно мемоізує довжину 5 на цій позиції та правило X. Після помилки на d, правило B, не спускаючись знову до X, запитує позицію 0 для правила X в механізмі мемоізаці, що повертає довжину 5 та запобігає повторному спуску до X, і продовжує працювати так, ніби воно зійшло до X стільки разів, скільки й раніше.
У наведеному вище прикладі може відбуватися одне або безліч спусків до X, що допускає рядки, такі як xxxxxxxxxxxxxxxxbd. Насправді, може бути будь-яке число x перед b. Хоча виклик S повинен рекурсивно опускатися до X стільки разів, скільки x зустрічається у рядку, B ніколи не доведеться спускатися до X, оскільки виклик ПравилоПриймаєДеякіВходи(X, 0, xxxxxxxxxxxxxxxxbd) поверне 16 (у цьому випадку).
Парсери, які використовують синтаксичні предикати[en], також можуть мемоізувати результати аналізу предикатів, тим самим зменшуючи конструкції наступного вигляду:
S → (A)? A A → /* деяке правило */
до одного спуску до A.
Якщо синтаксичний аналізатор будує дерево розбору під час розбору, він повинен мемоізувати не тільки довжину відповідних вхідних даних на деякій позиції відносно певного правила, але також повинен зберігати піддерево, яке генерується цим правилом, оскільки наступні виклики правила синтаксичного аналізатора насправді не спускатимуться та не будуватимуть це дерево.
Оскільки не всі граматики потребують пошуку з вертанням та перевірки предикатів, накладні витрати на зберігання результатів розбору кожного правила відносно кожної позиції у вхідних даних (та зберігання дерева розбору, якщо процес розбору робить це неявно) може в результаті уповільнити парсер. Цей ефект можна пом'якшити явним вибором тих правил, які парсер має мемоізувати.[13]
- Теорія складності обчислень — більше інформації про складність алгоритмів.
- Легковаговик (шаблон проектування) — шаблон проектування, який також використовує своєрідну мемоізацію.
- Ліниві обчислення — поділяє деякі поняття з мемоізацією.
- Часткові обчислення[en] — пов'язана техніка автоматичної оптимізації програм.
- Таблиця пошуку — структура даних з ключем, яка використовується в мемоізації.
- Hashlife[en] — мемоізований алгоритм для прискорення обчислення клітинних автоматів.
- ↑ а б в Norvig, Peter, "Techniques for Automatic Memoization with Applications to Context-Free Parsing [Архівовано 6 травня 2019 у Wayback Machine.], " Computational Linguistics, Vol. 17 No. 1, pp. 91–98, March 1991.
- ↑ Warren, David. «Tabling and Datalog Programming [Архівовано 2 лютого 2013 у Wayback Machine.]». Accessed 29 May 2009.
- ↑ Michie, Donald, "Memo Functions and Machine Learning [Архівовано 14 лютого 2019 у Wayback Machine.], " Nature, No. 218, pp. 19–22, 1968.
- ↑ Hoffman, Berthold, "Term Rewriting with Sharing and Memoïzation, " Algebraic and Logic Programming: Third International Conference, Proceedings, H. Kirchner and G. Levi (eds.), pp. 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), pp. 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 [Архівовано 22 серпня 2018 у Wayback Machine.]. " «Canadian Conference on AI 2003.» p 66-80.
- ↑ Johnson, Mark, "Memoization of Top-Down Parsing, " Computational Linguistics, Vol. 21 No. 3, pp. 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 [Архівовано 31 березня 2020 у Wayback Machine.], 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, pp. 14–25, 15–17 January 2003.
- Приклади мемоізації в різних мовах програмування
- groovy.lang.Closure#memoize() — функція
memoizeприсутня у мові програмування Apache Groovy 1.8. - Memoize [Архівовано 22 серпня 2018 у Wayback Machine.] — невелика бібліотека, написана Тимом Бредшоу, для виконання мемоізації в мові Common Lisp.
- IncPy [Архівовано 4 березня 2016 у Wayback Machine.] — інтерпретатор Python, який виконує автоматичну мемоізацію (без необхідних анотацій).
- Macros for defining memoized procedures [Архівовано 8 травня 2019 у Wayback Machine.] — макрос Дейва Германа для визначення мемоізованих процедур у мові Racket.
- Memoize.pm [Архівовано 12 серпня 2013 у Wayback Machine.] — модуль Perl, що реалізує мемоізовані функції.
- Java memoization [Архівовано 6 травня 2018 у Wayback Machine.] — приклад в Java з використанням динамічних проксі класів для створення загального шаблону мемоізації.
- memoization.java [Архівовано 12 червня 2018 у Wayback Machine.] — бібліотека мемоізації для Java.
- C++Memo[недоступне посилання з жовтня 2019] — фреймворк мемоізації для C++.
- C-Memo [Архівовано 8 травня 2019 у Wayback Machine.] — загальна бібліотека мемоізації для С, реалізована з використанням передпроцесорних макросів для обгортки функцій.
- Tek271 Memoizer [Архівовано 8 травня 2019 у Wayback Machine.] — механізм мемоізації для Java з відкритим вихідним кодом, який використовує анотації та кешування.
- memoizable [Архівовано 11 червня 2018 у Wayback Machine.] — бібліотека для Ruby, яка реалізує мемоізацію методів.
- Python memoization [Архівовано 24 листопада 2005 у Wayback Machine.] — приклад мемоізації в Python.
- Memoization in Lua [Архівовано 16 липня 2019 у Wayback Machine.] — два приклади реалізації загальної функції мемоізації в Lua.
- Memoization in Mathematica [Архівовано 8 травня 2019 у Wayback Machine.] — мемоізація та обмежена мемоізація в Mathematica.
- Memoization in Javascript — мемоізація в JavaScript (архівована версія http://talideon.com/weblog/2005/07/javascript-memoization.cfm).
- Memoization in Javascript [Архівовано 8 травня 2019 у Wayback Machine.] — приклади мемоізації в JavaScript з використанням кешування та бібліотеки YUI.
- X-SAIGA (eXecutable SpecificAtIons of GrAmmars) [Архівовано 4 квітня 2013 у Wayback Machine.] — містить публікації, пов'язані з алгоритмом низхідного синтаксичного аналізу, який підтримує ліву рекурсію і неоднозначність за поліноміальний час і простір.
- Memoization in Scheme [Архівовано 14 червня 2010 у Wayback Machine.] — приклад мемоізації в Scheme.
- Memoization in Combinatory Logic [Архівовано 15 листопада 2011 у Wayback Machine.] — вебсервіс для редукування комбінаторної логіки, який мемоізує кожний крок у базі даних.
- MbCache [Архівовано 26 червня 2013 у Wayback Machine.] — кешування результатів методів у .NET.