Мемоізація функції

JavaScriptJunior~3 хв читання

Мемоізація це техніка оптимізації, за якої функція запам'ятовує результати своїх викликів і повертає готове значення замість повторного обчислення. У JavaScript її будують на замиканні: зовнішня функція створює кеш, а внутрішня перевіряє його перед тим, як звернутися до оригінальної функції.

Теорія

TL;DR

Мемоізація це кеш «аргументи -> результат», який живе у замиканні обгортки.
Ключ кешу зазвичай будують через JSON.stringify(args), сховищем краще брати Map, а не звичайний об'єкт.
Працює коректно лише для чистих функцій: результат має залежати виключно від аргументів.
Кеш без обмежень росте нескінченно, тому в реальному коді додають ліміт (стратегія LRU).
Найпомітніший виграш, це рекурсія з перекриттям підзадач, наприклад числа Фібоначчі.
Асинхронні функції кешують не результат, а сам Promise, щоб паралельні виклики не запускали два запити.

Швидкий приклад

javascript

function memoize(fn) {
  const cache = {};

  return function (...args) {
    const key = JSON.stringify(args); // будуємо ключ з аргументів

    if (key in cache) {
      console.log('from cache:', key);
      return cache[key];
    }

    console.log('computing:', key);
    const result = fn(...args);
    cache[key] = result;
    return result;
  };
}

function slowAdd(a, b) {
  // імітація важких обчислень
  for (let i = 0; i < 1e8; i++);
  return a + b;
}

const memoAdd = memoize(slowAdd);

console.log(memoAdd(2, 3)); // computing
console.log(memoAdd(2, 3)); // from cache
console.log(memoAdd(4, 5)); // computing

Повторні виклики з тими самими аргументами більше не перераховуються, значення просто береться з пам'яті.

Базова реалізація: замикання плюс сховище

Будь-яка мемоізація складається з трьох частин:

Частина	Роль
Замикання	Тримає кеш живим між викликами обгортки
Ключ	Перетворює список аргументів на щось порівнюване (рядок)
Сховище	`Object` або `Map`, де лежать пари ключ-значення

Об'єкт як сховище простий, але має неприємні особливості: ключі завжди приводяться до рядка, а успадковані властивості на кшталт toString або constructor можуть випадково «знайтися» в кеші. Тому універсальніший варіант, це Map:

javascript

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

Переваги Map: немає конфліктів з прототипом, є чесний size, ключі зберігають порядок вставки (це знадобиться для LRU), а видалення через delete працює швидше, ніж delete obj[key].

Обмеження розміру кешу: LRU

Кеш без ліміту, це витік пам'яті: кожен новий набір аргументів додає запис, який ніколи не звільняється. Простий LRU (least recently used) виселяє найдавніше використаний запис, коли кеш переростає ліміт. Map тут ідеальний, бо ітерується в порядку вставки: щоб «освіжити» запис, достатньо видалити його й вставити наново, і він опиниться в кінці.

javascript

function memoize(fn, limit = 5) {
  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 > limit) {
      const oldestKey = cache.keys().next().value;
      cache.delete(oldestKey);
    }

    return result;
  };
}

Тепер кеш «ковзний»: він зберігає останні N викликів, що для реальних застосунків зазвичай саме те, що потрібно.

Мемоізація рекурсії: числа Фібоначчі

Найяскравіший приклад виграшу, це рекурсія, у якій підзадачі перекриваються. Наївний fib(n) обчислює ті самі значення експоненційну кількість разів.

javascript

function memoize(fn) {
  const cache = {};
  return function (n) {
    if (n in cache) return cache[n];
    const result = fn(n);
    cache[n] = result;
    return result;
  };
}

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

console.log(fib(40)); // швидко, попри рекурсію

Без мемоізації це були б десятки мільйонів викликів, а з кешем, лише близько 40. Зверніть увагу на іменований функціональний вираз function f: рекурсивний виклик має йти через ту саму обгортку, інакше внутрішні виклики оминуть кеш і оптимізація зникне.

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

Коли треба кешувати результати fetch або запиту до бази, кешувати слід Promise, а не значення. Інакше два одночасні виклики з тим самим ключем встигнуть стартувати два мережеві запити, бо перший ще не завершився і кеш порожній.

javascript

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).then(result => {
      cache.set(key, result);
      return result;
    });

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

Приклад використання:

javascript

const fetchUser = memoizeAsync(async (id) => {
  const res = await fetch(`https://api.example.com/users/${id}`);
  return res.json();
});

await fetchUser(1); // перший раз, HTTP-запит
await fetchUser(1); // другий раз, миттєво з кешу

Окремо варто продумати помилки: якщо fn відхилиться, відхилений Promise залишиться в кеші назавжди. Тому в продакшн-версії відхилений ключ видаляють через .catch(err => { cache.delete(key); throw err; }).

Коли мемоізація виправдана

Сценарій	Підходить?	Чому
Дорогі обчислення	Так	Прискорює повторні виклики
Аргументи повторюються	Так	Саме тут кеш дає виграш
Щоразу різні аргументи	Ні	Кеш лише марно займає пам'ять
HTTP-запити, база даних	З обережністю	Можна, якщо дані змінюються рідко
Великі обсяги даних	З обережністю	Стежте за пам'яттю, потрібен ліміт

Коротко: мемоізація це обмін пам'яті на процесорний час. Перш ніж додавати її, варто виміряти, чи справді функція є вузьким місцем.

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

Мемоізувати нечисту функцію. Якщо результат залежить від часу, випадкових чисел, стану модуля або зовнішнього запиту, кеш віддаватиме застаріле значення. memoize(() => Date.now()) назавжди зафіксує першу мітку часу.
Забути про обмеження кешу. Мемоізація у довгоживучому процесі (сервер, SPA) без ліміту, це класичний витік пам'яті.
Рекурсивно викликати оригінал, а не обгортку. Якщо всередині рекурсії викликати початкову функцію, кеш заповнюватиметься, але ніколи не читатиметься, і виграшу не буде.
Сліпо довіряти JSON.stringify як ключу. Порядок ключів в об'єктах впливає на рядок, тож {a: 1, b: 2} і {b: 2, a: 1} дадуть різні ключі. Крім того, undefined, функції та Symbol зникають при серіалізації, а циклічні структури кидають помилку.
Тримати сильні посилання на об'єкти-аргументи. Якщо кешувати за самим об'єктом, збирач сміття не звільнить його; для такого випадку є WeakMap, який не заважає збиранню сміття.
Кешувати асинхронний результат замість Promise. Тоді паралельні виклики все одно зроблять кілька запитів, бо запис у кеш з'явиться лише після відповіді.
Застосовувати мемоізацію до дешевих функцій. Обчислення ключа через JSON.stringify саме по собі коштує часу, тож обгортка над (a, b) => a + b працюватиме повільніше за оригінал.

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

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

Premium

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