Mi az a memoization és hogyan valósítod meg?

Question

Accepted Answer

**Memoization** egy függvény eredményeit az argumentumaik szerint tárcsapolja meg, így az ugyanazokkal a bemenetekkel ismételt hívások azonnal a gyorsítótárazott eredményt adják vissza az újraszámítás helyett. **Memóriát cserél a sebességért** és csak **tiszta** függvények esetében működik (ugyanaz a bemenet → ugyanaz a kimenet, nincs mellékhatás).

## Egy általános 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
```

## Egy klasszikus nyereség: rekurzív 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
```

## Kompromisszumok és figyelmeztetések

- **Cache kulcs stratégia**: `JSON.stringify` nem működik függvényekhez, és az objektumok kulcsainak sorrendje számít. Az objektum argumentumok esetében a `WeakMap` (referencia alapján kulcsozva) elkerüli a memória szivárgást.
- **Korlátlan növekedés**: a gyorsítótár soha nem csökken — használj **LRU** gyorsítótárat hosszú futási folyamatok esetén.
- Csak akkor memorizálj, ha az újraszámítás valóban költséges és a bemenetek ismétlődnek.

## Miért fontos ez

A memoization mindenütt jelen van: React `useMemo`/`React.memo`, Reselect selectorok, dinamikus programozás.

A koncepció (tiszta eredmények gyorsítótárazása bemenet szerint) ugyanaz; a művészet a kulcs kiválasztása és a gyorsítótár korlátozása.