На этом шаге мы рассмотрим, что такое мемоизация и что она нам даст.
Мемоизация - это метод, при котором сохраняются результаты выполненных вычислений, так что, когда они снова понадобятся, их можно найти, вместо того чтобы вычислять во второй (или миллионный) раз (рисунок 1).
Рис.1. Механизм мемоизации для людей
Термин "мемоизация" придумал Дональд Мичи - известный британский специалист в области информатики. Источник: Michie D. Memo functions: a language
feature with "rote-learning" properties. - Edinburgh University, Department of Machine Intelligence and Perception, 1967.
Создадим новую версию функции Фибоначчи, которая использует словарь Python для целей мемоизации.
from typing import Dict memo: Dict[int, int] = {0: 0, 1: 1} # базовые случаи def fib3(n: int) -> int: if n not in memo: memo[n] = fib3(n - 1) + fib3(n - 2) # мемоизация return memo[n] if __name__ == "__main__": print(fib3(5)) print(fib3(50))
Теперь можно смело вызывать fib3(50):
5
12586269025
Вызов fib3(20) даст только 39 вызовов fib3(), а не 21891, как в случае вызова fib2(20). Словарь memo изначально заполняется базовыми вариантами 0 и 1, избавляя fib3() от излишней сложности, связанной со вторым оператором if.
На следующем шаге мы рассмотрим автоматическую мемоизацию.
