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

JavaScript~4 хв читання

Мемоізація (memoization) зберігає результати функції в кеші за ключем з аргументів. При повторному виклику з тими ж аргументами функція повертає кешований результат без повторних обчислень.

Теорія

TL;DR

Аналогія: шеф-кухар, який записує рецепт після першого приготування страви. Те саме замовлення наступного разу він бере з нотаток.
Вимога: функція має бути чистою. Однаковий вхід завжди дає однаковий результат.
Головний компроміс: пам'ять проти швидкості. Кеш без обмежень росте до витоку пам'яті.
Використовуй коли обчислення займає >10ms і однакові аргументи повторюються в >5% викликів.
Пропускай для: простої арифметики, функцій з побічними ефектами, рідко повторюваних аргументів.

Базовий приклад

javascript

function memoize(fn) {
  const cache = {};
  return (...args) => {
    const key = JSON.stringify(args);
    if (key in cache) return cache[key];     // Попадання в кеш: без обчислень
    return (cache[key] = fn(...args));       // Промах: обчислити і зберегти
  };
}

const slowDouble = (n) => { /* важка робота */ return n * 2; };
const fastDouble = memoize(slowDouble);

fastDouble(5);  // Обчислено: 10
fastDouble(5);  // З кешу: 10, нуль обчислень
fastDouble(9);  // Новий ключ, обчислено: 18

Повернута функція тримає об'єкт cache через замикання (closure). При попаданні в кеш повертає результат за O(1). При промаху запускає оригінальну функцію і зберігає результат.

Коли memoize(fn) виконується, воно створює замикання. Повернута функція захоплює cache із зовнішнього scope і тримає його живим стільки, скільки існує мемоізована функція, не чіпаючи глобальний простір імен.

JSON.stringify(args) перетворює список аргументів на стабільний рядковий ключ. [5, 10] стає "[5,10]". V8 оптимізує повторні звернення до об'єктів зі стабільною формою (hidden classes), тому попадання в кеш ефективно O(1) на практиці.

Одне реальне обмеження: JSON.stringify втрачає тип для Date, NaN, Symbol і undefined. NaN серіалізується як null, Symbol зникає повністю. Два різних аргументи можуть дати однаковий ключ. Для таких випадків потрібен власний серіалізатор або Map з ключами-тегами типів.

Коли застосовувати

Рекурсивні функції з перетинними підзадачами (числа Фібоначчі, обхід дерева): уникає експоненційного часу.
Чисті функції, що часто викликаються з однаковими аргументами (форматери, трансформери даних): пропускає однакову роботу.
Трансформери відповідей API, де сирі дані між викликами не змінюються: кеш за параметрами запиту.
Пропускай для: всього що читає Date.now(), генераторів випадкових чисел, функцій з I/O, простої арифметики.

Варіанти кешу

Звичайний об'єкт-кеш росте нескінченно. Для тривалих процесів (Node.js сервери, SPA) це реальна проблема. Два практичних патерни вирішують її.

LRU (витісняє найдавніший запис):

javascript

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(...args);
    cache.set(key, result);

    if (cache.size > maxSize) {
      cache.delete(cache.keys().next().value); // Видалити найстаріший запис
    }

    return result;
  };
}

TTL (записи закінчуються через певний час):

javascript

function memoizeWithTTL(fn, ttl = 5000) {
  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(...args);
    cache.set(key, { value: result, timestamp: Date.now() });
    return result;
  };
}

TTL підходить коли дані можуть застаріти, наприклад кешування відповіді API на 10 секунд.

Мемоізація в React

React має три вбудованих інструменти мемоізації. Кожен вирішує свою задачу.

React.memo обгортає компонент і пропускає повторний рендер, якщо пропси поверхнево рівні попередньому рендеру:

javascript

import { memo } from 'react';

const ProductList = memo(({ products, onSelect }) => {
  return (
    <ul>
      {products.map(p => (
        <li key={p.id} onClick={() => onSelect(p)}>{p.name}</li>
      ))}
    </ul>
  );
});
// Повторний рендер тільки якщо products або onSelect змінились

useMemo кешує обчислене значення всередині компонента. Перераховує тільки коли залежності змінюються:

javascript

import { useMemo } from 'react';

function Dashboard({ orders, activeStatus }) {
  const filtered = useMemo(
    () => orders.filter(o => o.status === activeStatus),
    [orders, activeStatus]
  );

  return <OrderTable data={filtered} />;
}

useCallback кешує саме посилання на функцію. Це важливо коли функція передається як проп у мемоізований дочірній компонент, бо нова функція при кожному рендері ламає memo дитини:

javascript

import { useCallback, memo, useState } from 'react';

const Button = memo(({ onClick, label }) => (
  <button onClick={onClick}>{label}</button>
));

function Parent() {
  const [count, setCount] = useState(0);

  const handleClick = useCallback(() => {
    setCount(prev => prev + 1);
  }, []); // Стабільне посилання між рендерами

  return <Button onClick={handleClick} label={`Кількість: ${count}`} />;
}

Найчастіша помилка яку я бачу: useMemo навколо count * 2. Це арифметика в наносекундах. Витрати на хук більші за виграш.

Типові помилки

Мемоізація нечистих функцій:

javascript

const getTime = memoize(() => Date.now());
getTime(); // Кешує перший timestamp
getTime(); // Повертає застарілий кешований час - неправильно

Мемоізація має сенс тільки коли однакові аргументи завжди дають однаковий результат.

Мутовані аргументи руйнують кеш:

javascript

function badMemo(fn) {
  const cache = {};
  return (arg) => {
    cache[arg.id] = fn(arg);
    arg.processed = true; // Мутує вхід після кешування
    return cache[arg.id];
  };
}
// Наступний виклик бачить мутований arg і повертає застарілий результат

Рішення: використовуй стабільний примітив як ключ (arg.id), не сам об'єкт.

Відсутність обмеження розміру в тривалому процесі:

javascript

const cache = {}; // Росте без обмежень в Node.js сервері
// Після навантаженого трафіку: 1GB+ heap, OOM краш

Рішення: пакет lru-cache з npm або LRU-реалізація вище.

JSON.stringify з датами або символами:

javascript

JSON.stringify([new Date()]); // Стає рядком, тип Date втрачено
JSON.stringify([Symbol('id')]); // '[null]' - Symbol зник
// Різні входи, однаковий ключ кешу: неправильні результати

Рішення: власний серіалізатор або рядкові ключі з тегами типів.

Де зустрічається

React 18: useMemo для фільтрації, сортування або агрегування великих списків.
Redux Toolkit / Reselect: createSelector мемоізує похідний стан у великих застосунках.
Lodash 4.17: _.memoize з кастомним resolver-ом, використовується в Webpack loaders для кешування парсингу.
Next.js 14: unstable_cache кешує запити даних в RSC, щоб один запит не виконувався знову при кожному рендері.
Express / Node.js: apicache middleware кешує GET-відповіді за URL і параметрами запиту.

Питання на співбесіді

Q: У чому різниця між мемоізацією і динамічним програмуванням?
A: Мемоізація йде зверху вниз: обчислює ліниво і кешує по дорозі. DP йде знизу вверх: заповнює таблицю від найменших підзадач наперед, не чекаючи запиту.

Q: Що станеться з пам'яттю при 1 мільйоні унікальних ключів кешу?
A: Приблизно 100MB для простих пар ключ-значення. Обмеж кеш через LRU або використовуй WeakMap, щоб GC міг прибирати записи коли аргументи-об'єкти більше ніде не використовуються.

Q: Чому JSON.stringify дає збій з NaN і Symbol?
A: NaN стає null, а Symbol зникає. Два різних входи можуть дати один рядковий ключ, що призводить до невірних попадань в кеш. Вирішується кастомним серіалізатором з тегами типів.

Q: У React, яка різниця між React.memo і useMemo?
A: React.memo це компонент вищого порядку, що пропускає повторний рендер за пропсами. useMemo це хук, що кешує обчислене значення всередині компонента за масивом залежностей. Різний scope, різний сценарій використання.

Q (senior): Як розшарити кеш мемоізації між кількома Node.js worker-процесами?
A: Redis з TTL на ключ через ioredis. Кожен процес читає і пише у спільне сховище. Для інвалідації кешу додай pub/sub канал або версіонований ключ коли базові дані змінюються.

Приклади

Числа Фібоначчі: без і з мемоізацією

javascript

// Без мемо: O(2^n) час
// fib(3) виконується 2 рази, fib(2) - 3 рази для fib(5)
function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

console.time('fib без мемо');
fib(40); // ~1500ms
console.timeEnd('fib без мемо');

// З мемо: O(n) час
// Кожна підзадача обчислюється рівно один раз
function memoize(fn) {
  const cache = {};
  return (...args) => {
    const key = JSON.stringify(args);
    if (key in cache) return cache[key];
    return (cache[key] = fn(...args));
  };
}

const fibMemo = memoize((n) => {
  if (n <= 1) return n;
  return fibMemo(n - 1) + fibMemo(n - 2);
});

console.time('fib з мемо');
fibMemo(40); // ~0.5ms
console.timeEnd('fib з мемо');

Мемоізована версія переходить від експоненційного до лінійного часу, бо кожне значення обчислюється один раз і зберігається. fibMemo(3) виконується рівно один раз незалежно від того, скільки більших викликів від нього залежить.

useMemo для фільтрації в React

javascript

import { useMemo, useState } from 'react';

function OrderDashboard({ orders }) {
  const [activeStatus, setActiveStatus] = useState('pending');

  // Без useMemo: фільтрує 10k записів при кожному рендері
  // З useMemo: перефільтровує тільки коли orders або activeStatus змінюються
  const filtered = useMemo(
    () => orders.filter(o => o.status === activeStatus),
    [orders, activeStatus]
  );

  return (
    <>
      <StatusTabs value={activeStatus} onChange={setActiveStatus} />
      <OrderTable data={filtered} />
    </>
  );
}

На датасеті з 10,000 записів фільтрація при кожному рендері додає помітну затримку. useMemo запускає її тільки коли щось справді змінюється.

TTL-кеш для повторних API-запитів

javascript

function memoizeWithTTL(fn, ttl = 5000) {
  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(...args); // Застарів або відсутній, обчислюємо
    cache.set(key, { value: result, timestamp: Date.now() });
    return result;
  };
}

const getUser = memoizeWithTTL(async (id) => {
  const res = await fetch(`/api/users/${id}`);
  return res.json();
}, 10_000); // Кешувати відповіді на 10 секунд

await getUser(42); // Запит до API
await getUser(42); // Повертає кешований результат (в межах 10с)
// Після 10 секунд: автоматично запросить свіжі дані

Цей патерн добре підходить для даних, що змінюються зрідка, але запитуються часто. TTL не дає застарілим даним жити надто довго.

Коротка відповідь

Для співбесіди

Premium

Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.

Дочитали статтю?