Memoize (с WeakMap для объектов)

Мемоизация появляется на собеседованиях в двух контекстах: оптимизация рекурсии (fibonacci) и кэширование дорогих вычислений в React/Vue. Интервьюер ждёт базовую Map-версию, обсуждение стратегии ключа для нескольких аргументов и понимание WeakMap — чтобы объекты-аргументы не удерживались от GC.

Базовая Map-мемоизация с настраиваемой функцией ключа:

/**
 * Кэширует результаты fn. Ключ строится из аргументов через JSON.stringify.
 * @param {Function} fn
 * @param {{ keyFn?: (...args: any[]) =&gt; string }} [opts]
 */
function memoize(fn, { keyFn = (...args) =&gt; JSON.stringify(args) } = {}) {
  const cache = new Map();

  function memoized(...args) {
    const key = keyFn(...args);
    if (cache.has(key)) return cache.get(key);
    const result = fn.apply(this, args);
    cache.set(key, result);
    return result;
  }

  memoized.cache  = cache;
  memoized.clear  = () =&gt; cache.clear();
  memoized.delete = (...args) =&gt; cache.delete(keyFn(...args));
  return memoized;
}

// Рекурсивная функция: рефакторинг ПОСЛЕ объявления через reassign
const fib = memoize(function self(n) {
  if (n &lt;= 1) return n;
  return self(n - 1) + self(n - 2); // self → уже замемоизирован
});
console.log(fib(40)); // мгновенно: O(n) вместо O(2^n)

// Кастомный keyFn: один строковый аргумент как ключ
const memoFetch = memoize(fetchUser, { keyFn: id =&gt; String(id) });
await memoFetch(42); // запрос
await memoFetch(42); // из кэша

WeakMap-trie для объектных аргументов — без утечек памяти:

// Проблема JSON.stringify для объектов:
// ─ { a: 1, b: 2 } vs { b: 2, a: 1 } → разные ключи (порядок ключей не нормализован)
// ─ Циклические ссылки → TypeError
// ─ Объекты удерживаются в Map бесконечно → утечка памяти

/**
 * Trie-based memoize: каждый объектный аргумент — узел в WeakMap,
 * примитивы — в обычной Map. Нет утечек, нет строк-ключей.
 */
function memoizeWeak(fn) {
  const root = makeNode();

  return function (...args) {
    let node = root;
    for (const arg of args) node = getOrCreate(node, arg);
    if (!node.hasValue) {
      node.value    = fn.apply(this, args);
      node.hasValue = true;
    }
    return node.value;
  };
}

function makeNode() {
  return { weak: new WeakMap(), prim: new Map(), value: undefined, hasValue: false };
}

function getOrCreate(node, arg) {
  const store =
    arg !== null &amp;&amp; (typeof arg === 'object' || typeof arg === 'function')
      ? node.weak
      : node.prim;
  if (!store.has(arg)) store.set(arg, makeNode());
  return store.get(arg);
}

// usage
const process = memoizeWeak((config, data) =&gt; heavyTransform(config, data));
const cfg = { locale: 'ru', tz: 'Europe/Moscow' };
process(cfg, [1, 2, 3]); // вычисляется
process(cfg, [1, 2, 3]); // из WeakMap-кэша по ссылке cfg
// Когда cfg выходит из области видимости — GC может собрать без утечки

LRU-ограничение кэша через Map iteration order:

// В продакшне кэш без лимита = утечка памяти при разнообразных входах.
// Map в JS итерируется в порядке вставки — используем для O(1) LRU.

function memoizeLRU(fn, maxSize = 100) {
  const cache = new Map(); // oldest → newest

  return function (...args) {
    const key = JSON.stringify(args);

    if (cache.has(key)) {
      const val = cache.get(key);
      cache.delete(key);   // удалить со старой позиции
      cache.set(key, val); // вставить в конец (newest)
      return val;
    }

    const result = fn.apply(this, args);
    cache.set(key, result);

    // Вытесняем LRU — первый ключ Map (oldest)
    if (cache.size &gt; maxSize) {
      cache.delete(cache.keys().next().value);
    }

    return result;
  };
}

// Резюме стратегий:
// JSON.stringify  → просто, не работает с объектами/циклами
// WeakMap-trie    → правильно для объектных аргументов, нет утечек
// LRU Map         → ограничение памяти, нужен JSON.stringify как ключ
// В реальном коде: lodash.memoize / memoize-one (один аргумент)

Сложность

Время: O(1) cache hit; O(k) miss при JSON.stringify k-аргументов
Память: O(n) без лимита; O(maxSize) с LRU-ограничением

Итог: Три стратегии: JSON.stringify (просто), WeakMap-trie (без утечек для объектов), LRU Map (ограничение памяти). В реальном коде — memoize-one или lodash.