Запропонувати правку

Покращити цю статтю

Допрацюйте відповідь до «Мемоізація функції». Ваші зміни проходять модерацію перед публікацією.

Потрібне підтвердження

Контент

Що ви змінюєте

Заголовок (UA)

Коротка відповідь (UA)

Показується над повною відповіддю для швидкого нагадування.

Відповідь (UA)

**Мемоізація це техніка оптимізації, за якої функція запам'ятовує результати своїх викликів і повертає готове значення замість повторного обчислення.** У 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-запити, база даних | З обережністю | Можна, якщо дані змінюються рідко |
| Великі обсяги даних | З обережністю | Стежте за пам'яттю, потрібен ліміт |

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

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

Markdown · перетягуйте зображення · ⌘B / ⌘I шорткати1055 слів

Для рев’юера

Примітка для модератора (необов’язково)

Бачить лише модератор. Прискорює рев’ю.