re:re:actable
Урок 022 минуты чтения

Что такое 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.

Документация

Wikipedia: Memoization.

Дочитали до конца?
Отметьте урок — прогресс сохранится в браузере.

Поиск

Поиск по урокам