Что такое мемоизация?

Мемоизация — это техника оптимизации, используемая в программировании для ускорения выполнения функций путем кэширования результатов их вызова при определенных входных параметрах.

При последующем вызове функции с теми же аргументами, что были использованы ранее, функция не вычисляет результат заново, а возвращает сохраненное (запомненное) значение из кэша.

Это особенно эффективно для ресурсоемких функций с детерминированным поведением (функций, которые всегда возвращают один и тот же результат для одних и тех же входных данных).

Преимущества:

• Ускорение выполнения ресурсоемких функций.
• Снижение нагрузки на процессор за счет избегания повторных вычислений.

Недостатки:

• Увеличение потребления памяти для хранения кэша.
• Может быть неэффективно для функций, которые часто вызываются с разными аргументами или меняют свое поведение.

Пример на JavaScript:

function fibonacci(n) { // Функциональное определение чисел Фибоначчи
  if (n <= 1) {
    return n;
  }
  return fibonacci(n - 1) + fibonacci(n - 2); // Рекурсивный вызов
}

// Мемоизированная версия функции fibonacci
function memoizedFibonacci(n, cache = {}) {
  if (n in cache) { // Проверяем, есть ли результат в кэше
    return cache[n];
  }

  if (n <= 1) {
    return n;
  }

  // Вычисляем и сохраняем результат в кэше
  cache[n] = memoizedFibonacci(n - 1, cache) + memoizedFibonacci(n - 2, cache);
  return cache[n];
}

// Сравнение скорости выполнения:
console.time('Без мемоизации');
fibonacci(40);
console.timeEnd('Без мемоизации'); // Значительно больше времени

console.time('С мемоизацией');
memoizedFibonacci(40);
console.timeEnd('С мемоизацией'); // Значительно меньше времени

В данном примере, без мемоизации, функция fibonacci пересчитывает одни и те же значения многократно. Мемоизированная версия memoizedFibonacci сохраняет вычисленные значения в объекте cache, значительно ускоряя последующие вызовы с теми же аргументами.