YaChudo

Мемоїзація

Переглядів: 0. Оновлено 06.11.2026.

Мемоїзація — це метод оптимізації, який переважно використовується для прискорення комп'ютерних програм шляхом зберігання результатів дорогих викликів функцій та повернення кешованого результату, коли виклики на однакових вхідних даних відбуваються знову. Мемоїзація також використовується в інших контекстах (та для цілей, відмінних від прискорення швидкості), наприклад, у простому взаємному рекурсивному спуску[1]. Хоча мемоїзація пов'язана з кешуванням, вона належить до конкретного випадку цієї оптимізації, яка відрізняє її від інших форм кешування, таких як буферизація або заміщення сторінок. У контексті деяких мов логічного програмування мемоїзація також відома як табулювання[2]; див. також таблицю пошуку.

Етимологія

Термін «мемоїзація» був придуманий Дональдом Мічі в 1968 році[3] та походить від латинського слова «memorandum» («пам'ятати»), яке зазвичай скорочують як «memo» в американській англійській мові, і таким чином несе сенс «перетворення результатів функції на щось, що слід пам'ятати».

Огляд

Мемоїзована функція «запам'ятовує» результати, що відповідають деякому набору конкретних вхідних даних. Наступні виклики з запам'ятованими вхідними даними повертають запам'ятований результат, а не обчислюють його наново, тим самим усувається початкова вартість усіх викликів функції з заданими параметрами, окрім найпершого виклику. Множина таких зв'язків, що запам'ятовуються, може бути фіксованих розмірів, та керуватись алгоритмом, який виконує оновлення, або може бути фіксованою множиною, залежною від природи функції та її використання. Функція може бути мемоїзована, якщо вона прозора по посиланнях; тобто, лише якщо виклик функції має точно такий же ефект, як і заміна виклику функції величиною, що повертається. (Однак існують особливі винятки для цього обмеження.) Оскільки мемоїзація часто використовує у своїй реалізації таблиці пошуку, мемоїзація заповнює свій кеш результатів прозоро на льоту, за потреби, а не заздалегідь.

Мемоїзація — це спосіб знизити часові витрати функції в обмін на вартість простору; мемоїзовані функції оптимізують швидкість шляхом використання пам'яті комп'ютера. Часова/просторова «вартість» алгоритмів має спеціальну назву в обчислювальній техніці: обчислювальна складність. Всі функції мають обчислювальну складність в часі (тобто, вони потребують часу для виконання) і в просторі.

Хоча відбувається просторово-часова домовленість (тобто, використаний простір збільшує швидкість), це відрізняється від деяких інших оптимізацій, які включають просторово-часову домовленість, таких, як зниження вартості операцій, в якій мемоїзація є оптимізацією часу виконання, а не компіляції. Крім того, зниження вартості операцій потенційно замінює дорогі операції, таку як множення, менш витратною операцією додавання, та результати економії можуть бути залежними від машин, тоді як мемоїзація є багатоплатформною стратегією, яка не залежить від машин.

Розглянемо наступний псевдокод функції, яка обчислює факторіал: 

функція факторіал (n — невід'ємне ціле число)
    якщо n = 0 тоді
        повернути 1 [за конвенцією 0! = 1]
    інакше
        повернути факторіал(n – 1) помножений на n [рекурсивно викликаємо факторіал з параметром n меншим на 1]

Для кожного цілого числа n такого, що n ≥ 0, кінцевий результат функції факторіал є інваріантним; у результаті виклику x = факторіал(3) змінна x завжди буде мати значення 6. Немемоїзована реалізація, наведена вище, з урахуванням природи рекурсивного алгоритму, вимагатиме n + 1 викликів факторіала для отримання результату, і кожен з цих викликів, своєю чергою, має пов'язану вартість часу виконання. Залежно від машини ця вартість може бути сумою:

  1. Вартість встановлення фрейму стека функціональних викликів.
  2. Вартість порівняння n з 0.
  3. Вартість віднімання 1 від n.
  4. Вартість встановлення рекурсивного фрейму стека функціональних викликів. (Як і вище.)
  5. Вартість множення результату рекурсивного виклику функції факторіал на n.
  6. Вартість зберігання повернутого результату для його використання контекстом виклику.

У немемоїзованій реалізації кожен виклик верхнього рівня функції факторіал включає сукупну вартість кроків 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[6]), автоматична мемоїзація може бути реалізована шляхом заміни (під час виконання) функції на її обчислене значення після того, як було обчислено значення для даного набору параметрів. Функція, що виконує цю заміну, може обгортати будь-яку прозору за посиланнями функцію. Розглянемо псевдокод (який передбачає, що функції є об'єктами першого класу): 

  функція мемоїзований-виклик (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) та таблиці в алгоритмі Кока—Янгера—Касамі, можна було б генерувати шляхом введення автоматичної мемоїзації до простого аналізатора зворотного рекурсивного спуску для вирішення проблеми експоненційної складності часу.[1] Основна ідея підходу Норвіга полягає в тому, що, коли парсер застосовується до входу, результат зберігається в пам'яті для подальшого повторного використання. Річард Фрост також використовував мемоїзацію для зменшення експоненціальної часової складності комбінаторів парсерів.[7] Він показав, що основні базові комбінатори парсерів можуть бути використані як будівельні блоки для побудови складних парсерів.[8][9] Це було знову досліджено в контексті парсингу в 1995 році Джонсоном і Дорре.[10][11] У 2002 році мемоїзація у контексті синтаксичного аналізу була глибоко вивчена Фордом.[12]

У 2007 році Фрост, Хафіз і Каллахан описали алгоритм низхідного аналізу, який використовує мемоїзацію для утримання надмірних обчислень для розміщення будь-якої форми неоднозначної контекстно-вільної граматики за поліноміальний час (Θ(n⁴) для ліворекурсивних та Θ(n³) для не ліворекурсивних граматик). Їх алгоритм низхідного аналізу також вимагає поліноміального простору для потенційно експоненціальних неоднозначних дерев розбору за допомогою «компактного представлення» і «групування місцевих неоднозначностей». Їх компактне представлення можна порівняти з компактним представленням Томіти висхідного аналізу.[13] Їхнє використання мемоїзації не тільки обмежується вилученням раніше обчислених результатів, коли парсер повторно застосовується до однієї позиції входу (що є необхідним для вимоги поліноміального часу), воно спеціалізується на виконанні наступних додаткових завдань:

  • Процес мемоїзації (який можна розглядати як «обгортку» навколо виконання будь-якого парсера) пристосовує зростальний прямий ліворекурсивний аналіз, встановлюючи обмеження глибини щодо вхідної довжини і поточної позиції входу.
  • Процедура алгоритму для пошуку у таблиці також визначає можливість повторного використання збереженого результату шляхом порівняння обчислювального контексту збереженого результату з поточним контекстом синтаксичного аналізатора. Це контекстне порівняння є ключем для пристосування непрямої (або прихованої) лівої рекурсії.
  • При виконанні успішного пошуку в таблиці, замість того, щоб повертати повний набір результатів, процес повертає лише посилання на фактичний результат і зрештою прискорює швидкість обчислення.
  • Під час оновлення таблиці мемоїзації, процес мемоїзації групує (потенційно експоненційні) неоднозначні результати і забезпечує вимогу поліноміального простору.

Фрост, Хафіз і Каллахан також описали реалізацію алгоритму в PADL'08 як набір функцій вищого порядку (які називаються комбінаторами парсерів) в Haskell, що дозволяє будувати безпосередньо виконувані специфікації контекстно-вільних граматик як мовних процесорів. Потужність їх поліноміального алгоритму для розміщення «будь-якої форми неоднозначної КВ граматики» за допомогою низхідного синтаксичного аналізу є необхідною для аналізу синтаксису та семантики під час обробки природних мов. Сайт X-SAIGA[14] має більше інформації про алгоритм і деталі його реалізації.

Хоча Норвіг збільшив потужність синтаксичного аналізатора через мемоїзацію, розширений синтаксичний аналізатор все ще вимагав багато часу для виконання, як алгоритм Ерлі, що демонструє випадок використання мемоїзації для цілей, відмінних від оптимізації швидкості. Джонсон і Дорре[11] продемонстрували ще одне таке застосування мемоїзації: використання мемоїзації для відкладання вирішення лінгвістичних обмежень до моменту в аналізі, де накопиченої інформації достатньо для вирішення цих обмежень. На відміну від цього, при застосуванні мемоїзації для оптимізації швидкості, Форд продемонстрував, що мемоїзація може гарантувати, що граматики розбіру виразів можуть аналізувати за лінійний час навіть ті мови, які призвели до поведінки у найгіршому випадку.[12]

Розглянемо наступну граматику: 

 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 (у цьому випадку).

Парсери, які використовують синтаксичні предикати, також можуть мемоїзувати результати аналізу предикатів, тим самим зменшуючи конструкції наступного вигляду: 

 S → (A)? A
 A → /* деяке правило */

до одного спуску до A.

Якщо синтаксичний аналізатор будує дерево розбору під час розбору, він повинен мемоїзувати не тільки довжину відповідних вхідних даних на деякій позиції відносно певного правила, але також повинен зберігати піддерево, яке генерується цим правилом, оскільки наступні виклики правила синтаксичного аналізатора насправді не спускатимуться та не будуватимуть це дерево.

Оскільки не всі граматики потребують пошуку з вертанням та перевірки предикатів, накладні витрати на зберігання результатів розбору кожного правила відносно кожної позиції у вхідних даних (та зберігання дерева розбору, якщо процес розбору робить це неявно) може в результаті уповільнити парсер. Цей ефект можна пом'якшити явним вибором тих правил, які парсер має мемоїзувати.[15]

Див. також

Примітки

  1. ↑ а б в 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.
  2. ↑ Warren, David. «Tabling and Datalog Programming [Архівовано 2 лютого 2013 у Wayback Machine.]». Accessed 29 May 2009.
  3. ↑ Michie, Donald, «Memo Functions and Machine Learning [Архівовано 14 лютого 2019 у Wayback Machine.],» Nature, No. 218, pp. 19–22, 1968.
  4. ↑ 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.
  5. ↑ 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.
  6. ↑ [1] [Архівовано 16 серпня 2019 у Wayback Machine.]
  7. ↑ Frost, Richard. and Szydlowski, Barbara. «Memoizing Purely Functional Top-Down Backtracking Language Processors.» «Sci. Comput. Program.» 1996 — 27(3): 263—288.
  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.
  9. ↑ Frost, Richard. «Monadic Memoization towards Correctness-Preserving Reduction of Search [Архівовано 22 серпня 2018 у Wayback Machine.].» «Canadian Conference on AI 2003.» p 66-80.
  10. ↑ Johnson, Mark, «Memoization of Top-Down Parsing,» Computational Linguistics, Vol. 21 No. 3, pp. 405—417, September 1995.
  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.
  12. ↑ а б Ford, Bryan, Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking [Архівовано 31 березня 2020 у Wayback Machine.], Master's thesis, Massachusetts Institute of Technology, September, 2002.
  13. ↑ Tomita, Masaru. «Efficient Parsing for Natural Language.» Kluwer, Boston, MA, 1985.
  14. ↑ [2] [Архівовано 4 квітня 2013 у Wayback Machine.]
  15. ↑ 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.

Посилання

Приклади мемоїзації в різних мовах програмування

Джерело: стаття у Вікіпедії та історія редагувань (автори).