Задача: 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) |
| функции, циклы, Map | JSON.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). Рекурсия — через мемоизированную обертку.