re:re:actable
Урок 033 минуты чтения

Задача: once и memoize

На этой странице
Кратко

once(fn) возвращает функцию, которая вызывает fn только при первом вызове, а затем всегда возвращает сохраненный результат. memoize(fn) кеширует результаты по аргументам: повторный вызов с теми же аргументами берет значение из кеша. В обоих случаях решение — замыкание; в memoize главное — выбрать ключ кеша (один примитивный аргумент, сериализация, пользовательский resolver) и не забыть про ограничение размера кеша.

Вопрос

Реализуйте once(fn) и memoize(fn, resolver?). Как сформировать ключ кеша для нескольких аргументов и объектов? Чем опасен неограниченный кеш?

once

function once(fn) {
  let called = false;
  let result;
 
  return function (...args) {
    if (!called) {
      called = true;
      result = fn.apply(this, args);
      fn = null;                       // отпустить ссылку для сборщика мусора
    }
    return result;
  };
}
 
const init = once(() => {
  console.log("инициализация");
  return 42;
});
init();  // "инициализация", 42
init();  // 42, без лога

memoize

function memoize(fn, resolver = (...args) => (args.length === 1 ? args[0] : JSON.stringify(args))) {
  const cache = new Map();
 
  function memoized(...args) {
    const key = resolver(...args);
    if (cache.has(key)) return cache.get(key);   // has, а не get: результат может быть undefined
    const result = fn.apply(this, args);
    cache.set(key, result);
    return result;
  }
 
  memoized.cache = cache;
  return memoized;
}
 
const slowSquare = (n) => {
  for (let i = 0; i < 1e7; i++);
  return n * n;
};
const fastSquare = memoize(slowSquare);
fastSquare(9);   // долго
fastSquare(9);   // мгновенно из кеша

Ключ кеша

АргументыКлюч
один примитивсам аргумент (Map различает 1 и "1")
несколько примитивовJSON.stringify(args) или `args.join("
объектыссылка как ключ (WeakMap) или пользовательский resolver (например, user.id)
функции, циклы, MapJSON.stringify не подходит — нужен resolver

Мемоизация рекурсии

const fib = memoize((n) => (n < 2 ? n : fib(n - 1) + fib(n - 2)));
fib(50);   // 12586269025 — быстро, O(n)

Рекурсивный вызов идет через мемоизированную обертку, поэтому каждое n вычисляется один раз.

LRU-ограничение

function memoizeLRU(fn, limit = 100) {
  const cache = new Map();
  return function (arg) {
    if (cache.has(arg)) {
      const value = cache.get(arg);
      cache.delete(arg);
      cache.set(arg, value);                 // переместить в конец как недавно использованный
      return value;
    }
    const value = fn.call(this, arg);
    cache.set(arg, value);
    if (cache.size > limit) cache.delete(cache.keys().next().value); // удалить самый старый
    return value;
  };
}

Доп. вопросы интервьюера

  • Почему has, а не проверка cache.get(key)? результатом может быть undefined, 0 или false.
  • Когда мемоизация вредна? для дешевых функций, нечистых функций, огромного числа уникальных аргументов.
  • Как мемоизировать async-функцию? кешировать Promise, при ошибке удалять ключ из кеша.

Что важно помнить

  • Мемоизировать можно только чистые функции.
  • Неограниченный кеш — утечка памяти; используйте LRU, TTL или WeakMap.
  • JSON.stringify не различает undefined и отсутствующее значение в объектах и зависит от порядка ключей.
  • Теория: мемоизация, замыкания.

Мини-шпаргалка

once: флаг called + сохраненный result. memoize: Map кеш, resolver для ключа, cache.has перед get, fn.apply(this, args). Объекты — WeakMap или resolver. Ограничивать размер (LRU). Рекурсия — через мемоизированную обертку.

Документация

MDN: Map, MDN: WeakMap, Lodash: memoize, Lodash: once.

Дочитали до конца?
Отметьте урок — прогресс сохранится в браузере.

Поиск

Поиск по урокам