Для чого потрібне "запам'ятовування проміжних результатів"?

АлгоритмиJunior~3 хв читання

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

Запам'ятовування проміжних результатів (мемоізація/кешування) потрібне, щоб не переобчислювати одні й ті самі підзадачі або запити багаторазово. Це знижує асимптотичну складність і затримки, зменшує навантаження на 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;
  }

  function set(key, value) {
    if (map.size >= capacity) {
      const oldestKey = map.keys().next().value;
      map.delete(oldestKey);
    }
    map.set(key, { value, expiresAt: Date.now() + ttlMs });
  }

  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 сценарії.

Підсумок

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

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

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

Premium

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