Co je to memoizace?

Memoizace je technika optimalizace používaná v programování ke zrychlení vykonávání funkcí ukládáním výsledků jejich volání s určitými vstupními parametry do cache.

Při následném volání funkce se stejnými argumenty, které byly použity dříve, funkce neprovádí výpočet znovu, ale vrací uloženou (zapamatovanou) hodnotu z cache.

To je obzvláště efektivní pro funkce, které jsou náročné na zdroje a mají deterministické chování (funkce, které vždy vrací stejný výsledek pro stejné vstupní údaje).

Výhody:

• Zrychlení náročných funkcí.
• Snížení zátěže procesoru tím, že se vyhýbá opakovaným výpočtům.

Nevýhody:

• Zvýšení spotřeby paměti pro uložení cache.
• Může být neefektivní pro funkce, které jsou často volány s různými argumenty nebo mění své chování.

Příklad v JavaScriptu:

function fibonacci(n) { // Funkční definice Fibonacciho čísel
  if (n <= 1) {
    return n;
  }
  return fibonacci(n - 1) + fibonacci(n - 2); // Rekurzivní volání
}

// Memoizovaná verze funkce fibonacci
function memoizedFibonacci(n, cache = {}) {
  if (n in cache) { // Kontrola, jestli je výsledek v cache
    return cache[n];
  }

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

  // Výpočet a uložení výsledku do cache
  cache[n] = memoizedFibonacci(n - 1, cache) + memoizedFibonacci(n - 2, cache);
  return cache[n];
}

// Porovnání rychlosti:
console.time('Bez memoizace');
fibonacci(40);
console.timeEnd('Bez memoizace'); // Výrazně delší čas

console.time('S memoizací');
memoizedFibonacci(40);
console.timeEnd('S memoizací'); // Výrazně kratší čas

V tomto příkladu, bez memoizace, funkce fibonacci opakovaně počítá stejné hodnoty. Memoizovaná verze memoizedFibonacci ukládá vypočtené hodnoty do objektu cache, což výrazně urychluje následné volání se stejnými argumenty.