Урок 242 минуты чтения
Мемоизация
На этой странице
Кратко
Мемоизация - техника оптимизации, при которой функция запоминает результаты для уже встречавшихся аргументов и возвращает их из кэша.
Вопрос
Что такое мемоизация?
Базовая идея
Если функция дорогая, но при одинаковых аргументах всегда возвращает одинаковый результат, его можно кэшировать.
function slowDouble(value) {
console.log("Вычисляем");
return value * 2;
}Мемоизированная версия:
function memoize(fn) {
const cache = new Map();
return function (arg) {
if (cache.has(arg)) {
return cache.get(arg);
}
const result = fn(arg);
cache.set(arg, result);
return result;
};
}
const double = memoize(slowDouble);
double(10); // вычисляет
double(10); // берет из кэшаПочему нужна чистая функция
Мемоизация хорошо работает с чистыми функциями.
function sum(a, b) {
return a + b;
}Если функция зависит от времени, случайности или внешнего состояния, кэш может вернуть устаревший результат.
function getNowPlus(value) {
return Date.now() + value;
}Такую функцию мемоизировать опасно.
Несколько аргументов
Простой вариант:
function memoize(fn) {
const cache = new Map();
return function (...args) {
const key = JSON.stringify(args);
if (cache.has(key)) {
return cache.get(key);
}
const result = fn.apply(this, args);
cache.set(key, result);
return result;
};
}Важно: JSON.stringify подходит не для всех аргументов, например плохо работает с функциями, undefined, Symbol и циклическими объектами.
Пример с рекурсией
function memoize(fn) {
const cache = new Map();
return function (n) {
if (cache.has(n)) return cache.get(n);
const result = fn(n);
cache.set(n, result);
return result;
};
}
const fib = memoize(function (n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
});
fib(40);Без кэша наивный Fibonacci делает много повторных вычислений.
Подводные камни
- кэш занимает память;
- нужно продумать ключ кэша;
- для объектов ключи сложнее, чем для примитивов;
- нечистые функции могут давать неверные данные;
- иногда кэш нужно очищать.
Что важно помнить
- Мемоизировать можно только чистые функции: результат должен зависеть только от аргументов.
- Кеш без ограничений растет бесконечно — используйте LRU,
WeakMapдля объектов-ключей или TTL. - Ключ для нескольких аргументов часто строят через
JSON.stringify(args), но это медленно и ломается на функциях и циклах. - В React мемоизация —
useMemo,useCallback,React.memo; React Compiler делает это автоматически.
Мини-шпаргалка
| Условие | Мемоизация подходит? |
|---|---|
| чистая функция | да |
| дорогие вычисления | да |
| часто повторяются аргументы | да |
| зависит от времени/API | осторожно |
| много уникальных аргументов | может разрастись кэш |
Документация
Дочитали до конца?
Отметьте урок — прогресс сохранится в браузере.