Мемоїзація — це метод оптимізації, який в основному використовується для прискорення комп'ютерних програм шляхом зберігання результатів дорогих викликів функцій та повернення кешованого результату, коли виклики на однакових вхідних даних відбуваються знову. Мемоізація також використовується в інших контекстах (та для цілей, відмінних від прискорення швидкості), наприклад, у простому взаємному рекурсивному спускуNorvig, Peter, "Techniques for Automatic Memoization with Applications to Context-Free Parsing , " Computational Linguistics, Vol. 17 No. 1, pp. 91–98, March 1991.. Хоча мемоізація пов'язана з кешуванням, вона відноситься до конкретного випадку цієї оптимізації, яка відрізняє її від інших форм кешування, таких як буферизація або заміщення сторінок. У контексті деяких мов логічного програмування мемоізація також відома як табулюванняWarren, David. «Tabling and Datalog Programming ». Accessed 29 May 2009.; див. також таблицю пошуку.
Етимологія Термін «мемоізація» був придуманий в 1968 роціMichie, Donald, "Memo Functions and Machine Learning , " Nature, No. 218, pp. 19–22, 1968. та походить від латинського слова «memorandum» («пам'ятати»), яке зазвичай скорочують як «memo» в американській англійській мові, і таким чином несе сенс «перетворення результатів функції на щось, що слід пам'ятати».
Огляд Мемоізована функція «запам'ятовує» результати, що відповідають деякому набору конкретних вхідних даних. Наступні виклики з запам'ятованими вхідними даними повертають запам'ятований результат, а не обчислюють його наново, тим самим усувається початкова вартість усіх викликів функції з заданими параметрами, окрім самого першого виклику. Множина таких зв'язків, що запам'ятовуються, може бути фіксованих розмірів, та керуватись алгоритмом, який виконує оновлення, або може бути фіксованою множиною, залежною від природи функції та її використання. Функція може бути мемоізована, якщо вона прозора по посиланнях; тобто, лише якщо виклик функції має точно такий же ефект, як і заміна виклику функції величиною, що повертається. (Однак існують особливі винятки для цього обмеження.) Оскільки мемоізація часто використовує у своїй реалізації таблиці пошуку, мемоізація заповнює свій кеш результатів прозоро на льоту, за потреби, а не заздалегідь.
Мемоізація — це спосіб знизити часові витрати функції в обмін на вартість простору; мемоізовані функції оптимізують швидкість шляхом використання пам'яті комп'ютера. Часова/просторова «вартість» алгоритмів має спеціальну назву в обчислювальній техніці: обчислювальна складність. Всі функції мають обчислювальну складність в часі (тобто, вони потребують часу для виконання) і в просторі.
Хоча відбувається просторово-часова домовленість (тобто, використаний простір збільшує швидкість), це відрізняється від деяких інших оптимізацій, які включають просторово-часову домовленість, таких, як , в якій мемоізація є оптимізацією , а не . Крім того, зниження вартості операцій потенційно замінює дорогі операції, таку як множення, менш витратною операцією додавання, та результати економії можуть бути залежними від машин, тоді як мемоізація є багатоплатформною стратегією, яка не залежить від машин.
Розглянемо наступний псевдокод функції, яка обчислює факторіал:
функція факторіал (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, для обчислення значень аргументів і мемоізації результатів функцій.
Автоматична мемоізація Хоча мемоізація може бути додана до функцій внутрішньо і явно комп'ютерним програмістом майже так само, як реалізована вищезазначена функція факторіал, прозорі по посиланнях функції також можуть бути автоматично мемоізовані зовні. Методи, застосовані Пітером Норвігом, використовуються не тільки в Common Lisp (мова, на якій його робота демонструвала автоматичну мемоізацію), але й в інших мовах програмування. Застосування автоматичної мемоізації також було формально вивчене при дослідженні рерайтингу термів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.
У мовах програмування, де функції є об'єктами першого класу (такі як Lua, Python та Perl ), автоматична мемоізація може бути реалізована шляхом заміни (під ) функції на її обчислене значення після того, як було обчислено значення для даного набору параметрів. Функція, що виконує цю заміну, може обгортати будь-яку прозору за посиланнями функцію. Розглянемо псевдокод (який передбачає, що функції є об'єктами першого класу):
функція мемоізований-виклик (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.значення[аргументи]
повернути мемоізована-версія
Примітка: деякі з описаних вище кроків можуть бути неявно керовані мовою реалізації та надані для ілюстрації.
Парсери