Какво е мемоизация?

Мемоизацията е техника за оптимизация, използвана в програмирането за ускоряване изпълнението на функции чрез кеширане на резултатите от техните извиквания при определени входни параметри.

При последващото извикване на функцията със същите аргументи, които са били използвани по-рано, функцията не изчислява резултата отново, а връща запазената (запомнената) стойност от кеша.

Това е особено ефективно за ресурсоемки функции с детерминирано поведение (функции, които винаги връщат един и същи резултат за едни и същи входни данни).

Предимства:

• Ускорява изпълнението на ресурсоемки функции.
• Намалява натоварването на процесора чрез избягване на повторни изчисления.

Недостатъци:

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

Пример на 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, което значително ускорява последващите извиквания с едни и същи аргументи.