Što je memoization i kako ga implementirati?

Question

IT Interview Practice · Accepted Answer

**Memoization** keširuje rezultate funkcije po njenim argumentima, tako da ponovljeni pozivi s istim ulazima odmah vraćaju keširani rezultat umjesto ponovnog računanja. Traži **memoriju za brzinu** i funkcionira samo za **čiste** funkcije (isti ulaz → isti izlaz, bez nuspojava).

## Generički memoize wrapper

```js
function memoize(fn) {
  const cache = new Map();
  return (...args) => {
    const key = JSON.stringify(args); // build a cache key from the arguments
    if (cache.has(key)) {
      return cache.get(key);          // cache hit — skip the work
    }
    const result = fn(...args);
    cache.set(key, result);
    return result;
  };
}

const slowSquare = n => { /* expensive */ return n * n; };
const fastSquare = memoize(slowSquare);
fastSquare(4); // computes → 16
fastSquare(4); // cached → 16 instantly
```

## Klasična pobjeda: rekurzivni Fibonacci

```js
const fib = memoize(n => (n < 2 ? n : fib(n - 1) + fib(n - 2)));
// turns exponential O(2^n) into roughly O(n) by caching subproblems
```

## Kompromisi i upozorenja

- **Strategija ključa cache-a**: `JSON.stringify` ne radi za funkcije, a redoslijed ključeva je bitan za objekte. Za objektivne argumente, `WeakMap` (ključan po referenci) izbjegava curenja memorije.
- **Neograničeni rast**: cache se nikada ne smanjuje — koristite **LRU** cache za dugoročne procese.
- Memoizirajte samo kada je ponovno računanje zaista skupo i ulazi se ponavljaju.

## Zašto je to važno

Memoization je svuda: React `useMemo`/`React.memo`, Reselect selektori, dinamičko programiranje.

Koncept (cache čistih rezultata po ulazu) je isti; vještina je odabir ključa i ograničavanje cache-a.

Generički memoize wrapper

Klasična pobjeda: rekurzivni Fibonacci

Kompromisi i upozorenja

Zašto je to važno

Povezana pitanja