Мемоизация - понятное объяснение и практические примеры

Введение

Мемоизация (memoization) — это прием оптимизации, при котором вы кешируете результаты вызовов функций и переиспользуете их при повторных вызовах с теми же аргументами. То есть вы как бы «запоминаете» уже посчитанные значения, чтобы не выполнять тяжелые вычисления заново.

Смотрите, идея очень проста:

• есть функция, которая при одинаковых входных данных всегда возвращает один и тот же результат;
• ее вычисление достаточно дорогое по времени (или по внешним запросам — в базу, по сети и т.д.);
• вы можете сохранить результат первого вызова и в дальнейшем просто брать его из памяти.

Давайте на протяжении статьи будем рассматривать мемоизацию как частный случай кеширования: кеш здесь «привязан» к конкретной функции и ее аргументам.

Дальше вы увидите:

• базовый принцип работы мемоизации;
• когда она полезна, а когда нет;
• простые реализации на JavaScript, Python и Go;
• типичные ошибки и способы их избежать;
• несколько паттернов использования — от рекурсивных функций до работы с API.

---

Что такое мемоизация и чем она отличается от кеширования

Базовая идея

Мемоизация — это:

• кеширование на уровне функции;
• ключом выступает набор аргументов функции;
• значение — результат вычисления функции с этими аргументами.

Важно, чтобы функция была детерминированной: один и тот же набор аргументов всегда дает один и тот же результат и не зависит от внешнего состояния. Такие функции называют чистыми.

Если функция:

• обращается к глобальным переменным;
• зависит от текущего времени;
• читает случайные числа;
• ходит в сеть или файловую систему;

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

Отличие от «общего» кеширования

Кеширование бывает разным: на уровне HTTP, базы данных, файлов, приложений. Мемоизация — это конкретный способ кеширования:

• «привязан» к функции и ее аргументам;
• обычно живет в оперативной памяти процесса;
• часто реализуется как обертка вокруг функции.

Классическое кеширование может быть:

• распределенным (Redis, Memcached);
• файловым;
• с отдельными политиками инвалидации (LRU, TTL и т.д.).

Мемоизация обычно проще и локальнее, зато дает быстрый выигрыш по времени выполнения кода в пределах одного процесса.

---

Когда мемоизация полезна

Типичные ситуации применения

Мемоизация особенно полезна, когда:

1. Функция «дорогая» по времени:

   • рекурсивные вычисления (фибоначчи, комбинаторика, динамическое программирование);
   • сложная математика, статистика;
   • парсинг, сериализация, преобразования больших структур.

2. Функция вызывается много раз с одинаковыми аргументами:

   • вычисления в циклах;
   • повторные вычисления тех же значений в разных частях программы;
   • шаблоны/рендеринг с одинаковыми входными данными.

3. Входные данные ограничены по множеству:

   • вы точно знаете, что возможных вариантов аргументов не так много;
   • пример: вычисление значений полинома для ограниченного диапазона x.

Когда ее лучше не применять

Мемоизация может и навредить, если:

• у функции почти всегда разные аргументы;
• вызов функции дешевый (несколько простых операций);
• память ограничена (например, сервер с большим количеством процессов);
• важнее использовать память под другие данные.

Давайте сформулируем простое правило: чем дороже вычисление и чем чаще повторяются аргументы, тем выгоднее мемоизация.

---

Простейшая реализация мемоизации

Общая идея реализации

Чтобы реализовать мемоизацию, вам нужно:

1. иметь хранилище (map, dict, object) для уже посчитанных значений;
2. уметь строить ключ по аргументам функции;
3. при вызове:
   • проверять, есть ли результат в хранилище;
   • если есть — вернуть его;
   • если нет — вычислить, сохранить, вернуть.

Теперь посмотрим на конкретные языки.

---

Мемоизация в JavaScript

Простой пример с одним аргументом

Здесь я размещаю простой пример мемоизации функции вычисления факториала:

// Обычная рекурсивная функция факториала без мемоизации
function factorial(n) {
  if (n < 0) {
    throw new Error('n должно быть неотрицательным');
  }
  if (n === 0 || n === 1) {
    return 1; // Базовый случай
  }
  return n * factorial(n - 1); // Рекурсивный вызов
}

Теперь обернем ее в мемоизацию:

// Функция-обертка для мемоизации
function memoize(fn) {
  const cache = new Map(); // Здесь храним результаты

  return function (arg) {
    // Проверяем, есть ли результат в кеше
    if (cache.has(arg)) {
      // Если есть - возвращаем сохраненный результат
      return cache.get(arg);
    }

    // Если нет - вычисляем
    const result = fn(arg);
    cache.set(arg, result); // Сохраняем в кеш
    return result;
  };
}

// Оборачиваем factorial в мемоизацию
const memoFactorial = memoize(factorial);

// Теперь memoFactorial будет кешировать результаты
console.log(memoFactorial(5)); // Вычислит и сохранит
console.log(memoFactorial(5)); // Возьмет из кеша

Как видите, здесь кеш ключуется по одному аргументу. Для целых чисел и строк это работает хорошо.

Мемоизация функций с несколькими аргументами

Если аргументов несколько, нужен общий ключ. Часто делают так — сериализуют аргументы в строку:

function memoizeMulti(fn) {
  const cache = new Map(); // Кеш для любых наборов аргументов

  return function (...args) {
    // Строим строковый ключ по всем аргументам
    const key = JSON.stringify(args); // Важно - порядок аргументов сохраняется

    if (cache.has(key)) {
      return cache.get(key); // Возвращаем из кеша
    }

    const result = fn.apply(this, args); // Вызываем оригинальную функцию
    cache.set(key, result); // Сохраняем результат
    return result;
  };
}

// Пример функции с двумя аргументами
function slowAdd(a, b) {
  // Представим, что это очень медленный расчет
  for (let i = 0; i < 1e7; i++) {} // Пустой цикл для имитации "тяжелой" работы
  return a + b;
}

const memoAdd = memoizeMulti(slowAdd);

console.time('first');
console.log(memoAdd(3, 4)); // Первый вызов - медленный
console.timeEnd('first');

console.time('second');
console.log(memoAdd(3, 4)); // Второй вызов - быстрый из кеша
console.timeEnd('second');

Обратите внимание: сериализация через JSON.stringify подходит не всегда:

• для объектов с разным порядком полей она может дать разный результат;
• для больших объектов ключ получается длинным.

Но для многих практических задач такой способ достаточно удобен.

Ограниченный кеш — простейший LRU

Если вы просто будете добавлять новые записи в кеш, он может вырасти до огромных размеров. Давайте сделаем простую реализацию кеша ограниченного размера:

function memoizeWithLimit(fn, limit = 100) {
  const cache = new Map(); // Map сохраняет порядок добавления ключей

  return function (...args) {
    const key = JSON.stringify(args);

    if (cache.has(key)) {
      // Для "эффекта" LRU можно обновлять порядок
      const value = cache.get(key);
      cache.delete(key);     // Удаляем старую запись
      cache.set(key, value); // Добавляем снова как "самую свежую"
      return value;
    }

    const result = fn.apply(this, args);

    // Если кеш переполнен - удаляем самый старый ключ
    if (cache.size >= limit) {
      const firstKey = cache.keys().next().value; // Первый добавленный ключ
      cache.delete(firstKey);
    }

    cache.set(key, result);
    return result;
  };
}

Теперь вы видите, как можно ограничить рост памяти, не отказываясь от мемоизации.

---

Мемоизация в Python

Базовая реализация через словарь

Давайте разберемся на примере. Самая прямая реализация:

# Обычная функция вычисления чисел Фибоначчи
def fib(n):
    if n < 0:
        raise ValueError("n должно быть неотрицательным")
    if n in (0, 1):
        return n
    return fib(n - 1) + fib(n - 2)

Эта функция работает очень медленно для больших n из-за экспоненциальной рекурсии.

Теперь добавим мемоизацию:

def memoize(fn):
    cache = {}  # Словарь для хранения результатов

    def wrapper(*args):
        # args - кортеж аргументов, он хешируемый и подходит как ключ
        if args in cache:
            return cache[args]  # Возвращаем сохраненный результат
        result = fn(*args)      # Вызываем оригинальную функцию
        cache[args] = result    # Сохраняем в кеш
        return result

    return wrapper

# Оборачиваем функцию fib с помощью декоратора
@memoize
def fib_memo(n):
    if n < 0:
        raise ValueError("n должно быть неотрицательным")
    if n in (0, 1):
        return n
    return fib_memo(n - 1) + fib_memo(n - 2)

Теперь вы увидите, что fib_memo(40) считается значительно быстрее, чем fib(40) без мемоизации.

Использование functools.lru_cache

В стандартной библиотеке Python уже есть готовый инструмент для мемоизации — декоратор lru_cache.

from functools import lru_cache

@lru_cache(maxsize=128)  # maxsize - максимальное количество записей в кеше
def fib_fast(n):
    if n < 0:
        raise ValueError("n должно быть неотрицательным")
    if n in (0, 1):
        return n
    return fib_fast(n - 1) + fib_fast(n - 2)


print(fib_fast(100))      # Очень быстро
print(fib_fast.cache_info())  # Покажет статистику кеша

Комментарии к коду:

• lru_cache использует политику «Least Recently Used» — «наименее недавно использованный»;
• когда кеш переполнен, самая «старая» по использованию запись удаляется;
• аргументы функции должны быть хешируемыми (это важное ограничение).

Если нужно отключить кеширование, вы можете вызвать:

fib_fast.cache_clear()  # Очищает кеш для данной функции

---

Мемоизация в Go

В Go нет встроенного декоратора, как в Python, но можно реализовать мемоизацию вручную. Покажу вам простой пример.

Мемоизация функции с одним аргументом

package main

import (
    "fmt"
    "sync"
)

// Тип функции, которую будем мемоизировать - принимает int и возвращает int
type IntFunc func(int) int

// memoizeIntFunc возвращает обертку над функцией с кешем
func memoizeIntFunc(fn IntFunc) IntFunc {
    cache := make(map[int]int) // Кеш в виде map
    var mu sync.Mutex          // Мьютекс для потокобезопасности

    return func(n int) int {
        mu.Lock()               // Блокируем доступ к кешу
        value, ok := cache[n]
        mu.Unlock()             // Разблокируем как можно раньше

        if ok {
            // Если значение в кеше есть - просто возвращаем его
            return value
        }

        // Если нет - считаем результат
        result := fn(n)

        mu.Lock()               // Снова блокируем для записи
        cache[n] = result
        mu.Unlock()

        return result
    }
}

// Пример "тяжелой" функции
func slowSquare(n int) int {
    // Здесь могла бы быть долгая операция
    return n * n
}

func main() {
    memoSquare := memoizeIntFunc(slowSquare)

    fmt.Println(memoSquare(10)) // Первый вызов - без кеша
    fmt.Println(memoSquare(10)) // Второй - из кеша
}

Здесь важно:

• мы используем sync.Mutex для защиты доступа к карте из нескольких горутин;
• кеш размещен внутри замыкания, поэтому «привязан» к конкретной функции.

Мемоизация с несколькими аргументами

В Go ключом карты может быть только хешируемый тип. Для нескольких аргументов обычно делают структурный ключ:

package main

import (
    "fmt"
    "sync"
)

// Структура-ключ для двух целых аргументов
type twoInts struct {
    a, b int
}

type TwoIntFunc func(int, int) int

func memoizeTwoIntFunc(fn TwoIntFunc) TwoIntFunc {
    cache := make(map[twoInts]int)
    var mu sync.Mutex

    return func(a, b int) int {
        key := twoInts{a: a, b: b} // Собираем ключ

        mu.Lock()
        value, ok := cache[key]
        mu.Unlock()

        if ok {
            return value
        }

        result := fn(a, b)

        mu.Lock()
        cache[key] = result
        mu.Unlock()

        return result
    }
}

func slowAdd(a, b int) int {
    // "Тяжелая" операция
    return a + b
}

func main() {
    memoAdd := memoizeTwoIntFunc(slowAdd)
    fmt.Println(memoAdd(2, 3)) // Считаем
    fmt.Println(memoAdd(2, 3)) // Берем из кеша
}

Обратите внимание, что структура twoInts выступает ключом map. Порядок полей важен: (a=2, b=3) и (a=3, b=2) — разные ключи.

---

Типичные сценарии использования мемоизации

Ускорение рекурсивных алгоритмов

Мемоизация особенно хорошо работает совместно с рекурсией. Возьмем классический пример — вычисление чисел Фибоначчи.

Без мемоизации сложность экспоненциальная: O(2^n). При добавлении мемоизации мы сводим ее к O(n), потому что каждое значение считаем ровно один раз.

На Python это выглядит так:

def memoize(fn):
    cache = {}

    def wrapper(n):
        if n in cache:
            return cache[n]  # Берем сохраненный результат
        result = fn(n)       # Вычисляем новую величину
        cache[n] = result    # Сохраняем
        return result

    return wrapper

@memoize
def fib(n):
    if n < 0:
        raise ValueError("n должно быть неотрицательным")
    if n in (0, 1):
        return n
    return fib(n - 1) + fib(n - 2)

Как только вы добавляете мемоизацию, каждое fib(k) для k от 0 до n вычисляется максимум один раз.

Динамическое программирование

Мемоизация — это «top-down» подход (сверху-вниз), а классическое динамическое программирование по таблице — «bottom-up» (снизу-вверх). Зачастую одна и та же задача может быть решена и так, и так.

Преимущество мемоизации:

• вы считаете только те подзадачи, которые реально понадобились;
• часто код выглядит проще за счет рекурсивной формулировки задачи.

Недостаток:

• используется стек вызовов, можно упереться в ограничение по глубине рекурсии;
• для некоторых задач заполнение таблицы вручную проще контролировать по памяти.

---

Ключи кеша и проблемы с аргументами

Хешируемость аргументов

Чтобы использовать аргументы как ключ, они должны:

• быть хешируемыми (в Python — иметь hash, в Go — подходить как ключ map, в JS — быть корректно сериализуемыми);
• быть неизменяемыми (immutable), если вы используете их напрямую.

Например, в Python список (list) нельзя использовать как ключ словаря:

cache = {}
args = [1, 2]

# Данный код вызовет ошибку TypeError - list не является хешируемым типом
# cache[args] = 42

Но вы можете превратить список в кортеж:

cache = {}
args = (1, 2)     # Кортеж - уже хешируемый
cache[args] = 42  # Так можно

В JS сложные объекты как ключ Map можно использовать напрямую, но тогда важно понимать, что ключом будет именно сам объект, а не его содержимое. Два разных, но одинаковых по структуре объекта будут разными ключами.

Сложные структуры данных

Если аргументы — сложные деревья, графы, большие объекты, то:

• сериализация их в строку может быть дорогой;
• сравнение или хеширование могут занимать много времени.

В таких случаях мемоизация может дать меньше выигрыша или даже замедлить программу из-за тяжелой работы с ключами кеша.

Варианты решений:

• свести аргументы к упрощенному, но однозначному представлению (например, ID вместо полного объекта);
• мемоизировать на другом уровне (по уже подготовленным данным).

---

Управление временем жизни кеша

Неограниченный кеш

Самая простая реализация — кеш, который живет до завершения процесса. Плюсы:

• минимальная сложность кода;
• предсказуемое поведение.

Минусы:

• потенциальная утечка памяти, если количество уникальных аргументов растет без ограничений;
• невозможно «освободить» редко используемые результаты.

Ограничение размера кеша (LRU и подобные)

Мы уже кратко посмотрели простой LRU в JavaScript. Общая идея:

• вы храните не только значения, но и порядок их использования;
• когда кеш переполнен, удаляете либо:
  • самые старые (FIFO),
  • либо наименее недавно использованные (LRU),
  • либо наименее часто используемые (LFU).

В Python lru_cache уже реализует LRU-логику, вы просто задаете maxsize.

Истечение по времени (TTL)

Иногда важно, чтобы данные не жили в кеше слишком долго. Например, если функция получает данные из внешнего источника, который периодически меняется. Тогда логика кеша может включать:

• timestamp последнего вычисления;
• TTL (time to live) — максимальный возраст записи.

Алгоритм:

• при чтении из кеша проверяете, не истек ли TTL;
• если истек — пересчитываете и обновляете запись.

---

Потокобезопасность и конкурентный доступ

Проблема гонок данных

Если функцию с мемоизацией вызывают из нескольких потоков или горутин:

• доступ к общему кешу должен быть синхронизирован;
• иначе возможны гонки данных (data races) и повреждение состояния.

В Go это решается мьютексами или sync.Map. В Python GIL частично защищает от одновременной записи, но логическая корректность кеша все равно может нарушаться в сложных случаях.

Стратегии синхронизации

• Глобальная блокировка на чтение и запись кеша:

  • проще всего реализовать;
  • может стать узким местом при большом количестве потоков.

• Раздельная блокировка для чтения и записи:

  • read-write lock (RWMutex в Go);
  • много считывателей могут одновременно читать кеш;
  • запись блокирует всех.

• Ленивая инициализация (single flight):

  • если два потока одновременно запросили значение, еще не посчитанное ранее, важно не посчитать его два раза;
  • решается дополнительным слоем координации.

---

Подводные камни и типичные ошибки

Мемоизация «грязных» функций

Если функция:

• пишет в базу;
• отправляет письма;
• логирует;
• меняет глобальное состояние;

то кеширование результата вызова не отменяет побочного эффекта. Если вы закешировали результат и перестали вызывать функцию, побочный эффект больше не произойдет.

Давайте посмотрим на упрощенный пример:

function sendEmail(userId) {
  // Здесь мог бы быть реальный код отправки письма
  console.log('Отправляем письмо пользователю', userId);
  return true; // Допустим, значит "успешно"
}

const memoSendEmail = memoize(sendEmail);

memoSendEmail(1); // Выполнит отправку
memoSendEmail(1); // Возьмет результат из кеша, письмо НЕ уйдет снова

Обратите внимание: мемоизировать такие функции опасно, потому что вы не получите повторный эффект, которого, возможно, ожидаете.

Рекомендация: мемоизируйте только функции без побочных эффектов или четко осознавайте, что вы делаете.

Переменный внешний контекст

Если функция зависит от текущего времени, конфигурации, которых может меняться в процессе работы, или глобальных флагов, то мемоизация может возвращать устаревший результат.

Пример в Python:

config = {"rate": 2}

def compute(x):
    return x * config["rate"]  # Функция зависит от глобальной конфигурации

memo_compute = memoize(compute)

print(memo_compute(10))  # При rate=2 -> 20

config["rate"] = 3       # Конфигурация изменилась
print(memo_compute(10))  # Все равно вернет 20 из кеша, а не 30

Проблема в том, что ключ кеша не учитывает изменение global config.

Решения:

• добавлять в ключ кеша версии или значения конфигурации;
• не мемоизировать функции, зависящие от меняющегося контекста;
• сбрасывать кеш при изменении глобальных параметров.

Избыточная мемоизация

Иногда мемоизацию добавляют «на всякий случай», не замеряя производительность. В результате:

• расход памяти растет;
• накладные расходы на работу с кешом превышают выгоду.

Полезно следовать такому процессу:

1. Сначала написать простой понятный код без оптимизации.
2. Провести профилирование, найти действительно узкие места.
3. Только затем аккуратно применять мемоизацию к конкретным функциям.

---

Практические рекомендации по использованию мемоизации

Шаги внедрения

1. Найдите функцию, которая:

   • часто вызывается;
   • работает относительно долго;
   • имеет детерминированное поведение.

2. Убедитесь, что:

   • аргументы можно корректно использовать как ключ;
   • рост памяти от кеша контролируем.

3. Реализуйте мемоизацию:

   • через обертку/декоратор;
   • либо вручную внутри функции.

4. Замерьте:

   • время работы до и после;
   • потребление памяти;
   • частоту кеш-хитов (попаданий).

5. При необходимости:

   • добавьте ограничение по размеру кеша;
   • добавьте очистку/инвалидацию.

Где мемоизация особенно эффективна

• Алгоритмические задачи (динамическое программирование, рекурсии).
• Генерация отчетов, где одни и те же данные пересчитываются многократно.
• Шаблонизаторы и рендеринг интерфейсов с одинаковыми входными данными.
• Конвертеры, парсеры и сериализаторы, работающие с повторяющимися структурами.

---

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

---

Частозадаваемые технические вопросы по теме мемоизации

1. Как сбросить кеш мемоизированной функции во время работы приложения

Добавьте в обертку метод очистки кеша. Пример на JavaScript:

function memoize(fn) {
  const cache = new Map();

  function wrapped(...args) {
    const key = JSON.stringify(args);
    if (cache.has(key)) {
      return cache.get(key);
    }
    const result = fn(...args);
    cache.set(key, result);
    return result;
  }

  // Метод очистки кеша
  wrapped.clearCache = () => cache.clear();

  return wrapped;
}

// Использование
const memoFn = memoize(x => x * 2);
memoFn(10);
memoFn.clearCache(); // Кеш очищен

Вы можете вызывать clearCache, когда меняется конфигурация или внешние данные.

2. Как мемоизировать асинхронные функции, возвращающие промисы

Кешируйте не результат, а сам промис:

function memoizeAsync(fn) {
  const cache = new Map();

  return async function(...args) {
    const key = JSON.stringify(args);

    if (cache.has(key)) {
      return cache.get(key); // Возвращаем уже существующий промис
    }

    const promise = fn(...args); // Вызываем исходную async-функцию
    cache.set(key, promise);     // Сохраняем промис в кеш
    return promise;
  };
}

Так вы избежите повторных запросов, пока первый еще выполняется.

3. Как мемоизировать методы классов, учитывая this

Ключ должен учитывать контекст:

function memoizeMethod(fn) {
  const cache = new WeakMap(); // Кеш на уровне объекта

  return function(...args) {
    let objCache = cache.get(this);
    if (!objCache) {
      objCache = new Map();
      cache.set(this, objCache);
    }

    const key = JSON.stringify(args);
    if (objCache.has(key)) {
      return objCache.get(key);
    }

    const result = fn.apply(this, args);
    objCache.set(key, result);
    return result;
  };
}

Таким образом у каждого экземпляра класса будет свой кеш.

4. Как избежать утечек памяти при мемоизации в Node.js сервисе

Основные шаги:

• ограничьте размер кеша (maxsize);
• используйте структуры с LRU (например, пакет lru-cache);
• периодически очищайте или пересоздавайте кеш;
• не храните в кеше огромные объекты, если можно хранить только их идентификаторы.

Пример с lru-cache:

const LRU = require('lru-cache');

function memoize(fn, options) {
  const cache = new LRU(options);

  return function(...args) {
    const key = JSON.stringify(args);
    if (cache.has(key)) return cache.get(key);
    const result = fn(...args);
    cache.set(key, result);
    return result;
  };
}

5. Как замерить эффективность мемоизации

Минимальный набор метрик:

• время выполнения до и после (performance.now, time, бенчмарки);
• количество вызовов функции по факту (обернуть функцию и увеличивать счетчик);
• количество кеш-хитов/промахов.

Пример на Python с lru_cache:

from functools import lru_cache

@lru_cache(maxsize=256)
def heavy(x):
    # тяжелая функция
    ...

# После серии вызовов
print(heavy.cache_info())  # Показаны hits, misses, maxsize, currsize

По этим цифрам вы поймете, насколько хорошо сработала мемоизация.