Термін Запам'ятовування походить від латинського слова меморандум ( пам'ятати ), що зазвичай скорочується до memo в американській англійській мові, що означає перетворення результатів функції на те, що потрібно запам’ятати.

В обчислювальній техніці мемоізація використовується для прискорення роботи комп’ютерних програм шляхом усунення повторного обчислення результатів і уникнення повторних викликів функцій, які обробляють той самий вхід.

Що таке мемоізація

Зміст

• Що таке мемоізація?
• Чому використовується мемоізація>
• Де використовувати Memoization?
• Типи запам'ятовування
• Як техніка запам'ятовування використовується в динамічному програмуванні?
  • Підхід зверху вниз
  • Підхід «знизу вгору».
• Чим Memoization відрізняється від Tabulation?
• Практичні задачі кодування для запам’ятовування
• поширені запитання
  • 1) Мемоізація краща за DP?
  • 2) Мемоізація – це те саме, що кешування?
  • 3) Чому запам'ятовування відбувається зверху вниз?
  • 4) Чи використовує мемоізація рекурсію?
  • 5) Мені використовувати табуляцію чи запам’ятовування?
  • 6) Де використовується мемоізація?
  • 7) Чому це називається запам’ятовуванням?
  • 8) Як запам’ятовування зменшує складність часу?
  • 9) Яка різниця між запам'ятовуванням і кешуванням?
  • 10) Чому зведення в таблиці швидше, ніж запам’ятовування?
• Висновок

Чому використовується мемоізація?

Мемоізація є специфічною формою кешування що використовується в динамічне програмування . Метою кешування є покращення продуктивності наших програм і забезпечення доступу до даних, які можна використовувати пізніше. В основному він зберігає попередньо обчислений результат підпроблеми та використовує збережений результат для тієї самої підзадачі. Це усуває зайві зусилля, щоб знову і знову обчислювати ту саму проблему. І ми вже знаємо, що якщо та сама проблема виникає знову і знову, то ця проблема рекурсивна за своєю природою.

Де використовувати Memoization?

Ми можемо використовувати техніку запам’ятовування, де використання попередньо обчислених результатів входить в картину. Цей вид задачі здебільшого використовується в контексті рекурсія , особливо з проблемами, які включають перекриваються підпроблеми .

Давайте візьмемо приклад, коли та сама підпроблема повторюється знову і знову.

Приклад, щоб показати, де використовувати запам’ятовування:

  Let us try to     find the factorial of a number    .>

Нижче a рекурсивний метод для знаходження факторіала числа:

int факторіал (unsigned int n)
{
якщо (n == 0)
повернення 1;
повернути n * факторіал (n – 1);
}

Що станеться, якщо ми використаємо цей рекурсивний метод?

Якщо ви напишете повний код для наведеного вище фрагмента, ви помітите, що в коді буде 2 методи:

1. factorial(n) 2. main()>

Тепер, якщо у нас є кілька запитів для визначення факторіалу, наприклад, визначення факторіала 2, 3, 9 і 5, тоді нам потрібно буде викликати метод factorial() 4 рази:

factorial(2) factorial(3) factorial(9) factorial(5)>

Рекурсивний метод знаходження Факторіала

Таким чином, можна з упевненістю сказати, що для знаходження факторіала чисел K чисел буде потрібно час O (N*K)

• O(N) щоб знайти факторіал певного числа, і
• СТРІЛКА) щоб викликати метод factorial() K різних разів.

Як Memoization може допомогти з такими проблемами?

Якщо ми помітимо у наведеній вище задачі під час обчислення факторіалу 9:

карти java

• Ми обчислюємо факторіал 2
• Ми також обчислюємо факторіал 3,
• і ми також обчислюємо факторіал 5

Тому, якщо ми збережемо результат кожного окремого факторіала під час першого обчислення, ми можемо легко повернути факторіал будь-якого необхідного числа лише за O(1) час. Цей процес відомий як Запам'ятовування .

Рішення з використанням Memoization (Як працює Memoization?):

Якщо ми спочатку знайдемо факторіал числа 9 і збережемо результати окремих підзадач, ми зможемо легко надрукувати факторіал кожного входу в O(1).

Тому пошук факторіалів за допомогою запам’ятовування складний у часі O(N)

• O(N) щоб знайти факторіал найбільшого входу
• О(1) щоб надрукувати факторіал кожного входу.

Типи запам'ятовування

Реалізація запам'ятовування залежить від змінних параметрів, які відповідають за вирішення проблеми. Існують різні параметри кешування, які використовуються в техніці запам’ятовування. Нижче наведено деякі з них:

• 1D Memoization: Рекурсивна функція, яка має лише один аргумент, значення якого не було постійним після кожного виклику функції.
• 2D Memoization: Рекурсивна функція, яка має лише два аргументи, значення яких не було постійним після кожного виклику функції.
• 3D Memoization : рекурсивна функція, яка має лише три аргументи, значення яких не були постійними після кожного виклику функції.

Як техніка запам'ятовування використовується в динамічному програмуванні?

Динамічне програмування допомагає ефективно вирішувати проблеми, які мають перекриваючі підзадачі та оптимальні властивості підструктури. Ідея динамічного програмування полягає в тому, щоб розбити проблему на менші підпроблеми та зберегти результат для майбутнього використання, таким чином усуваючи необхідність багаторазового обчислення результату.

Існує два підходи до формулювання рішення динамічного програмування:

1. Підхід зверху вниз: Цей підхід слідує запам'ятовування техніка . Він складається з рекурсія і кешування . У обчисленнях рекурсія представляє процес повторного виклику функцій, тоді як кеш відноситься до процесу зберігання проміжних результатів.
2. Підхід «знизу вгору»: Цей підхід використовує табулювання техніка реалізувати рішення динамічного програмування. Він вирішує ті самі проблеми, що й раніше, але без рекурсії. У цьому підході ітерація замінює рекурсію. Отже, немає помилки переповнення стеку або накладних витрат на рекурсивні процедури.

Як техніка Memoization використовується в динамічному програмуванні

Чим Memoization відрізняється від Tabulation?

Табуляція проти мемоізації

Для отримання додаткової інформації зверніться до: Табуляція проти мемоізації

Практичні задачі кодування на запам'ятовуванні

Часті запитання (FAQ) про Memoization

1: Мемоізація краща за DP?

Запам'ятовування - це низхідний підхід до вирішення проблеми за допомогою динамічного програмування. Це називається запам’ятовуванням, тому що ми створимо пам’ятку для значень, отриманих у результаті вирішення кожної проблеми.

2: Мемоізація – це те саме, що кешування?

Запам'ятовування - це фактично специфічний тип кешування. Термін «кешування» загалом може стосуватися будь-якої техніки зберігання (наприклад, кешування HTTP) для майбутнього використання, але запам’ятовування стосується більш конкретно функції кешування, яка повертає значення.

3: Чому запам'ятовування відбувається зверху вниз?

Підхід «зверху вниз» розбиває велику проблему на кілька підпроблем. якщо підпроблему вже вирішено, то повторно використовуйте відповідь. В іншому випадку розв’яжіть підзадачу та збережіть результат у пам’яті.

4. Чи використовує мемоізація рекурсію?

Запам'ятовування дотримується підходу зверху вниз до вирішення проблеми. Він складається з рекурсії та кешування. У обчисленнях рекурсія представляє процес повторного виклику функцій, тоді як кеш відноситься до процесу зберігання проміжних результатів.

5: Мені використовувати табуляцію чи мемоізацію?

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

6: Де використовується мемоізація?

Запам’ятовування — це техніка оптимізації, яка використовується для прискорення комп’ютерних програм шляхом кешування результатів дорогих викликів функцій і повернення їх, коли ті самі вхідні дані зустрічаються знову.

7: Чому це називається запам’ятовуванням?

Термін мемоізація походить від латинського слова memorandum (запам’ятовувати), яке в американській англійській мові зазвичай скорочується до memo, що означає перетворення результатів функції у те, що потрібно запам’ятати.

8: Як запам’ятовування зменшує складність часу?

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

9: Яка різниця між запам’ятовуванням і кешуванням?

Насправді мемоізація — це певний тип кешування, який передбачає кешування значення, що повертається функцією, на основі вхідних даних. Кешування є більш загальним терміном. Наприклад, кешування HTTP є кешуванням, але не запам’ятовуванням.

10: Чому зведення в таблиці швидше, ніж запам’ятовування?

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

Запам'ятовування — це техніка, яка використовується в інформатиці для прискорення виконання рекурсивних або обчислювально дорогих функцій шляхом кешування результатів викликів функцій і повернення кешованих результатів, коли повторюються ті самі вхідні дані.

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

Ось покроковий посібник із впровадження мемоізації:

Визначте функцію, яку потрібно оптимізувати за допомогою запам’ятовування. Ця функція повинна мати повторні та дорогі обчислення для того самого входу.

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

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

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

Повернути обчислений результат.

Ось приклад коду Python для реалізації запам’ятовування за допомогою словника:

Python3

>

>

>

У наведеному вище коді ми визначаємо функцію під назвою Фібоначчі, яка обчислює n-е число в послідовності Фібоначчі. Ми використовуємо об’єкт словника під назвою кеш для зберігання результатів викликів функцій. Якщо вхідний параметр n уже присутній у кеш-словнику, ми повертаємо кешований результат. В іншому випадку ми обчислюємо результат за допомогою рекурсивних викликів функції Фібоначчі та зберігаємо його в кеш-словнику перед поверненням.

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

Висновок

Мемоізація — це концепція програмування, яку можна застосувати до будь-якої мови програмування. Її абсолютна мета – оптимізація програми. Зазвичай ця проблема виникає, коли програми виконують важкі обчислення. Ця техніка кешує всі попередні обчислені результати, щоб не потрібно було повторно обчислювати для тієї самої проблеми.

Схожі статті:

• Мемоізація за допомогою декораторів у Python
• Запам'ятовування JavaScript