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

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

Допрацюйте відповідь до «Для чого потрібне "запам'ятовування проміжних результатів"?». Ваші зміни проходять модерацію перед публікацією.

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

Контент

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

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

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

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

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

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

**Запам'ятовування проміжних результатів** (мемоізація/кешування) потрібне, щоб не переобчислювати одні й ті самі підзадачі або запити багаторазово. Це знижує асимптотичну складність і затримки, зменшує навантаження на CPU/пам'ять/мережу/БД, підвищує відгукливість інтерфейсу і масштабованість системи.

## Розгорнуте пояснення

### Що це таке

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

### Де це застосовують у веброзробці

- Алгоритми та структури даних: динамічне програмування, мемоізація рекурсивних функцій (наприклад, Fibonacci, шляхи на графах).
- UI/Frontend: memo/useMemo/useCallback у React, мемоізація селекторів (наприклад, обчислення похідних даних зі стору), кешування результатів форматування і сортування.
- Backend/Node.js: кешування відповідей API, кеш гарячих даних із БД, кешування шаблонів і результатів серіалізації, LRU-кеші в пам'яті, Redis як зовнішній кеш.
- Бази даних: матеріалізовані подання, query cache на рівні застосунку, денормалізація з подальшою синхронізацією.
- Інфраструктура та білди: інкрементальні збірки, кешування артефактів CI/CD, кешування NPM/Yarn, HTTP-кешування статики (ETag, Cache-Control).

### Навіщо це потрібно (плюси)

- Зниження часу виконання і затримок за рахунок усунення повторних обчислень/запитів.
- Покращення асимптотики (наприклад, експонента -> лінійна для деяких рекурсивних задач).
- Зниження навантаження на CPU/пам'ять/мережу/БД, економія бюджету і квот.
- Підвищення відгукливості інтерфейсу і пропускної здатності бекенду.

### Компроміси та ризики

- Пам'ять: кеш займає RAM; можливі витоки під час зберігання великих ключів/значень.
- Актуальність: ризик застарілих даних; потрібна інвалідація (TTL/версії/події).
- Складність: проєктування ключів кешу, політика витіснення (LRU/LFU), обробка конкуренції.
- Чистота функцій: мемоізація коректна для детермінованих операцій без побічних ефектів.
- Stampede/дублювання роботи: під час "штормів" кешу один і той самий розрахунок може запускатися багатьма клієнтами; корисна дедуплікація запитів у польоті (in-flight).

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

- Є повторні виклики з однаковими входами (особливо дорогі обчислення).
- Часто читані й рідко змінювані дані (read-heavy навантаження).
- Повільні I/O операції: запити в мережу, БД, файлову систему.
- Не підходить, якщо дані майже завжди унікальні, або якщо сувора консистентність важливіша за швидкість.

## Приклади коду

### JavaScript: проста мемоізація функції

```javascript
function memoize(fn, keyResolver = (...args) => JSON.stringify(args)) {
  const cache = new Map();
  return function memoized(...args) {
    const key = keyResolver(...args);
    if (cache.has(key)) return cache.get(key);
    const result = fn.apply(this, args);
    cache.set(key, result);
    return result;
  };
}

// Приклад: штучно "дорога" функція
const slowSquare = (n) => {
  for (let i = 0; i < 1e7; i++); // імітація навантаження
  return n * n;
};

const memoSquare = memoize(slowSquare);
console.time('first');
console.log(memoSquare(12345));
console.timeEnd('first');

console.time('second (from cache)');
console.log(memoSquare(12345));
console.timeEnd('second (from cache)');
```

### Динамічне програмування: Fibonacci з мемоізацією і без

```javascript
// Наївна рекурсія: експоненційна складність ~O(phi^n)
function fibNaive(n) {
  return n <= 1 ? n : fibNaive(n - 1) + fibNaive(n - 2);
}

// Мемоізація: зберігаємо проміжні результати
const fibMemo = (function () {
  const memo = new Map([[0, 0], [1, 1]]);
  function f(n) {
    if (memo.has(n)) return memo.get(n);
    const val = f(n - 1) + f(n - 2);
    memo.set(n, val);
    return val;
  }
  return f;
})();

console.time('naive 40');
fibNaive(40);
console.timeEnd('naive 40');

console.time('memo 40');
fibMemo(40);
console.timeEnd('memo 40');

// З мемоізацією складність стає O(n) за часом і O(n) за пам'яттю.
```

### React: useMemo/useCallback для дорогих обчислень і стабільних пропів

```tsx
import React, { useMemo, useCallback } from 'react';

function Products({ products, query }) {
  const normalizedQuery = useMemo(() => query.trim().toLowerCase(), [query]);

const visible = useMemo(
    () => products.filter(p => p.name.toLowerCase().includes(normalizedQuery)),
    [products, normalizedQuery]
  );

const onAddToCart = useCallback((id) => {
    // обробник не створюється заново на кожному рендері
    // ...
  }, []);

return (
    <ul>
      {visible.map(p => (
        <Product key={p.id} product={p} onAddToCart={onAddToCart} />
      ))}
    </ul>
  );
}

// Пояснення:
// - useMemo кешує результат фільтрації, доки не зміняться залежності.
// - useCallback кешує саму функцію-обробник для оптимізації дочірніх мемо-компонентів.
```

### Node.js: кешування відповідей API (in-memory LRU + TTL)

```javascript
function makeLRU(capacity = 1000, ttlMs = 60_000) {
  const map = new Map(); // key -> { value, expiresAt }

function get(key) {
    const entry = map.get(key);
    if (!entry) return undefined;
    if (entry.expiresAt < Date.now()) { map.delete(key); return undefined; }
    // оновлюємо "свіжість"
    map.delete(key);
    map.set(key, entry);
    return entry.value;
  }

return { get, set };
}

const cache = makeLRU(500, 10_000);

async function fetchJsonCached(url, options = {}) {
  const key = url + ':' + JSON.stringify(options);
  const cached = cache.get(key);
  if (cached) return cached;

const res = await fetch(url, options);
  if (!res.ok) throw new Error(res.statusText);
  const data = await res.json();
  cache.set(key, data);
  return data;
}

(async () => {
  console.time('first');
  await fetchJsonCached('https://api.example.com/users?limit=50');
  console.timeEnd('first');

console.time('cached');
  await fetchJsonCached('https://api.example.com/users?limit=50');
  console.timeEnd('cached');
})();

// У реальному сервісі додайте дедуплікацію одночасних запитів і стратегію інвалідації.
```

## Інвалідація та стратегії кешування

- TTL (time-to-live): простий і надійний спосіб закінчення терміну дії за часом.
- Cache-aside: застосунок спочатку дивиться в кеш, у разі промаху - у джерело, потім записує в кеш.
- Write-through/Write-back: запис через кеш або відкладений запис; балансування консистентності та продуктивності.
- Версіонування ключів: інвалідація за зміною версії даних/схеми (наприклад, user:123:v2).
- LRU/LFU: витіснення найменш недавно/часто використовуваних записів для контролю RAM.

## Як відповісти на співбесіді

- Дайте визначення: зберігання результатів підзадач для запобігання повторним обчисленням (мемоізація/кешування).
- Наведіть алгоритмічний приклад: Fibonacci - з мемоізацією складність O(n) замість експоненти.
- Пов'яжіть із веброзробкою: React useMemo/useCallback, кеш відповідей API/БД (Redis/LRU), HTTP-кеш статики.
- Зазначте компроміси: пам'ять, інвалідація, консистентність, ключі, конкуренція і stampede.
- Сформулюйте критерії застосування: повторюваність входів, дороговизна операції, read-heavy сценарії.

## Підсумок

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

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

Для рев’юера

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

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