Šta je memoizacija?

Мемоизација је техника оптимизације која се користи у програмирању за убрзање извршавања функција кроз кеширање резултата њихових позива са одређеним улазним параметрима.

Када се функција позове касније са истим аргументима као раније, функција не израчунава резултат поново, већ враћа сачувану (запамћену) вредност из кеша.

Ово је посебно ефикасно за ресурсо-емне функције са детерминистичким понашањем (функције које увек враћају исти резултат за исте улазне податке).

Предности:

• Убрзава извршавање ресурсо-емних функција.
• Смањује оптерећење процесора избегавањем поновних израчунавања.

Недостаци:

• Повећава потрошњу меморије за чување кеша.
• Може бити неефикасно за функције које се често позивају са различитим аргументима или мењају своје понашање.

Пример у 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, што значајно убрзава следећа позивања са истим аргументима.