Пример (JavaScript): универсальная функция memoize и пример для рекурсивного вычисления чисел Фибоначчи.
Код:
```js
// Простая универсальная мемоизация для функций с произвольным числом аргументов.
// Использует Map и JSON.stringify как ключ (подходит для простых сериализуемых аргументов).
function memoize(fn, resolver) {
const cache = new Map();
return function(...args) {
const key = resolver ? resolver(...args) : JSON.stringify(args);
if (cache.has(key)) return cache.get(key);
const result = fn.apply(this, args);
cache.set(key, result);
return result;
};
}
// Пример: рекурсивный Fibonacci (неэффективно без мемоизации)
const fib = memoize(function(n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
});
console.log(fib(40)); // быстро благодаря кешированию
```
Краткое обсуждение, когда мемоизация улучшает производительность, а когда ухудшает.
Когда улучшает:
- Для чистых (deterministic) функций, где одинаковые входы всегда дают одинаковый выход — повторные вызовы возвращают результат из кеша.
- Для дорогостоящих вычислений, которые часто повторяются (динамическое программирование). Пример: для рекурсивного Fibonacci время падает с экспоненциального $O({\phi }^n)$ до линейного $O(n)$.
- Если множество возможных аргументов невелико относительно числа вызовов — выигрыш по времени заметен.
Когда может ухудшить:
- Память: кеш хранит результаты для каждого уникального набора аргументов, поэтому память растёт до числа уникальных вызовов $m$ — примерно $O(m)$.
- Стоимость управления ключами: создание/серилизация ключа (например, `JSON.stringify`) и сравнение могут добавлять накладные расходы $O(k)$ по длине аргумента, поэтому для лёгких вычислений мемоизация может быть медленнее.
- Нечистые функции (зависят от внешнего состояния или времени): кеш будет выдавать устаревшие значения — нужна инвалидация кеша или вообще не использовать мемоизацию.
- Большие или неограниченные пространства аргументов: кеш разрастается, нужен LRU/TTL/лимит по памяти; иначе возможен OOM.
- Потокобезопасность/синхронизация в многопоточной среде — необходимость блокировок/атомарных операций может добавить накладные расходы.
Рекомендации:
- Применять к чистым дорогостоящим функциям с повторяющимися аргументами.
- Для объектов/ссылок использовать Map/WeakMap или пользовательский resolver вместо сериализации.
- Ограничивать кеш (LRU, TTL) при потенциально большом домене аргументов.
- Иметь возможность очистить кеш при смене внешних данных.