Мемоизация

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

Зачем нужно

Мемоизация ускоряет повторные вычисления за счёт памяти. Для дорогостоящих операций (сложные расчёты, обращения к API, парсинг) кэширование результата может дать ускорение в десятки и сотни раз.

Где используется

Рекурсивные алгоритмы (Fibonacci, динамическое программирование), React.memo и useMemo, вычисление селекторов (Redux reselect), кэш запросов, парсинг шаблонов.

Предпосылки

Замыкания (Closures), Чистые функции, Рекурсия

Ручная реализация

Простая мемоизация (один аргумент)

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;
  };
}

// Использование
function heavyComputation(n) {
  console.log(`Вычисляю для ${n}...`);
  let result = 0;
  for (let i = 0; i < n * 1000000; i++) {
    result += Math.sqrt(i);
  }
  return result;
}

const memoized = memoize(heavyComputation);

console.time('first');
memoized(100);  // "Вычисляю для 100..." — вычисление
console.timeEnd('first');  // ~200ms

console.time('second');
memoized(100);  // из кэша — моментально
console.timeEnd('second'); // ~0.01ms

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

function memoize(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;
  };
}

const add = memoize((a, b) => {
  console.log('Вычисляю...');
  return a + b;
});

add(1, 2); // "Вычисляю..." → 3
add(1, 2); // из кэша → 3
add(2, 1); // "Вычисляю..." → 3 (другой ключ!)

WeakMap для объектных аргументов

function memoizeWithWeakMap(fn) {
  const cache = new WeakMap();

  return function(obj) {
    if (cache.has(obj)) {
      return cache.get(obj);
    }
    const result = fn(obj);
    cache.set(obj, result);
    return result;
  };
}

// WeakMap не мешает сборке мусора
const processUser = memoizeWithWeakMap((user) => {
  console.log('Обработка пользователя...');
  return {
    fullName: `${user.first} ${user.last}`,
    initials: `${user.first[0]}${user.last[0]}`
  };
});

const user = { first: 'Иван', last: 'Петров' };
processUser(user); // "Обработка пользователя..."
processUser(user); // из кэша (тот же объект по ссылке)

Мемоизация рекурсии

Fibonacci без мемоизации — O(2^n)

function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

// fib(40) — ~1 секунда, fib(50) — зависание

Fibonacci с мемоизацией — O(n)

function fibMemo(n, memo = new Map) {
  if (memo.has(n)) return memo.get(n);
  if (n <= 1) return n;

  const result = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  memo.set(n, result);
  return result;
}

console.log(fibMemo(100)); // 354224848179262000000 — мгновенно

Автоматическая мемоизация рекурсивных функций

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

  function memoized(...args) {
    const key = JSON.stringify(args);
    if (cache.has(key)) return cache.get(key);
    // Передаём memoized вместо fn для рекурсивных вызовов
    const result = fn(memoized, ...args);
    cache.set(key, result);
    return result;
  }

  return memoized;
}

const fib = memoizeRecursive((self, n) => {
  if (n <= 1) return n;
  return self(n - 1) + self(n - 2);
});

console.log(fib(100)); // мгновенно

Продвинутые реализации

С ограничением размера кэша (LRU)

function memoizeLRU(fn, maxSize = 100) {
  const cache = new Map();

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

    if (cache.has(key)) {
      // Перемещаем в конец (самый новый)
      const value = cache.get(key);
      cache.delete(key);
      cache.set(key, value);
      return value;
    }

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

    if (cache.size >= maxSize) {
      // Удаляем самый старый (первый элемент Map)
      const oldestKey = cache.keys().next().value;
      cache.delete(oldestKey);
    }

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

С TTL (время жизни кэша)

function memoizeTTL(fn, ttl = 60000) {
  const cache = new Map();

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

    if (cached && Date.now() - cached.timestamp < ttl) {
      return cached.value;
    }

    const result = fn.apply(this, args);
    cache.set(key, { value: result, timestamp: Date.now() });
    return result;
  };
}

// Кэш API-запроса на 5 минут
const fetchUser = memoizeTTL(async (id) => {
  const res = await fetch(`/api/users/${id}`);
  return res.json();
}, 5 * 60 * 1000);

С пользовательским ключом

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

  return function(...args) {
    const key = keyFn ? keyFn(...args) : JSON.stringify(args);
    if (cache.has(key)) return cache.get(key);

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

// Ключ по ID пользователя, не по всему объекту
const getUserRole = memoize(
  (user) => expensiveLookup(user),
  (user) => user.id  // кэш по id
);

Когда использовать

Ситуация Мемоизация
Чистая функция с дорогим вычислением Да
Рекурсия с перекрывающимися подзадачами Да
Частые вызовы с одинаковыми аргументами Да
Функция с побочными эффектами Нет
Функция с уникальными аргументами Нет (кэш бесполезен)
Функция с огромным числом вариантов Осторожно (память)

Частые ошибки

1. Мемоизация функции с побочными эффектами

let callCount = 0;
const impure = memoize((x) => {
  callCount++; // побочный эффект!
  return x * 2;
});

impure(5); // callCount = 1
impure(5); // callCount всё ещё 1! Побочный эффект потерян

2. Неправильный ключ для объектов

const bad = memoize((obj) => obj.value * 2);

const a = { value: 5 };
const b = { value: 5 };

bad(a); // вычисляет
bad(b); // тоже вычисляет! Разные объекты = разные ключи JSON

3. Утечка памяти без ограничений

// Кэш растёт бесконечно
const leaky = memoize((id) => fetchData(id));

// За 24 часа может накопиться гигабайты
// Решение: используй memoizeLRU или memoizeTTL

4. Мемоизация в горячем цикле

// JSON.stringify на каждый вызов — может быть дороже самого вычисления
const trivial = memoize((a, b) => a + b);
// Для простых операций мемоизация — overhead

Практика

  1. Реализуй memoize(fn) для функции с одним аргументом
  2. Добавь поддержку нескольких аргументов
  3. Мемоизируй рекурсивную функцию подсчёта путей в сетке
  4. Реализуй мемоизацию с TTL (время жизни записи)
  5. Напиши мемоизированную функцию fibonacci и сравни время с обычной

Связанные темы

Ресурсы

🎓 Источник: Memoizing Functions memoize

  • 📅 2019-11-19 · YouTube · ID: H6S8QJo2Qxg
  • Тезисы:
    • Мемоизация — кэш результатов чистой функции по ключу аргументов
    • Реализация через замыкание: внешняя функция хранит cache, возвращает обёртку
    • Кэш растёт неограниченно — нужно ограничение (LRU, TTL, WeakMap)
    • Применима только к чистым функциям; с побочными эффектами — ломает поведение
    • Каррирование и мемоизация — независимые декораторы, можно компоновать