Что такое memoization?
На этой странице
Memoization - кеширование результатов функции для уже решенных подзадач. Она превращает повторяющуюся рекурсию в более эффективный top-down dynamic programming.
Вопрос
Что такое memoization и как она ускоряет рекурсивные решения?
Проблема Fibonacci
function fib(n: number): number {
if (n <= 1) return n
return fib(n - 1) + fib(n - 2)
}Без memoization много повторных вычислений. Дерево вызовов для fib(5):
fib(5)
/ \
fib(4) fib(3)
/ \ / \
fib(3) fib(2) fib(2) fib(1)
/ \ ... ...
fib(2) fib(1)
...fib(3) считается 2 раза, fib(2) - 3 раза. С ростом n повторов становится экспоненциально больше: fib(30) без кеша делает около 2,7 миллиона вызовов, а с кешем - 59. Сложность наивной версии примерно O(2^n).
С memoization
function fib(n: number, memo = new Map<number, number>()): number {
if (n <= 1) return n
if (memo.has(n)) return memo.get(n)!
const value = fib(n - 1, memo) + fib(n - 2, memo)
memo.set(n, value)
return value
}Сложность:
Time: O(n)
Space: O(n)Теперь каждое fib(k) вычисляется один раз, а все повторные вызовы сразу возвращают ответ из memo. Дерево вызовов превращается почти в прямую линию.
Когда нужна memoization?
- есть рекурсия;
- есть одинаковые подзадачи;
- результат подзадачи зависит от параметров;
- brute force повторяет работу;
- можно построить ключ состояния.
Ключ состояния
const key = `${i}:${j}`
memo.set(key, result)Для нескольких параметров нужно аккуратно кодировать state.
Что отвечать на собеседовании?
Memoization кеширует ответы подзадач, чтобы не вычислять их повторно. Это top-down DP: мы оставляем рекурсивную структуру, но добавляем Map или массив для cache. Ключ cache должен однозначно описывать состояние.
Что важно помнить: частые ошибки
- Кешировать не все параметры состояния.
- Использовать object key как строку случайно.
- Не возвращать cached value.
- Мутировать state, который используется как key.
- Не учитывать memory
O(number of states).
Мини-шпаргалка
- Memo = cache.
- Top-down DP.
- Key = state.
- Повторные подзадачи исчезают.
- Time часто states * transition.
- Space = cache + recursion stack.