Hva er memoization og hvordan implementerer du det?

Question

IT Interview Practice · Accepted Answer

**Memoization** cacher resultatet av en funksjon nøkklet av argumentene, slik at gjentatte oppkall med samme input returnerer det cachede resultatet instant i stedet for å beregne på nytt. Det handler om å bytte **minne for hastighet** og fungerer bare for **rene** funksjoner (samme input → samme output, ingen bivirkninger).

## En generisk 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
```

## Et klassisk eksempel: rekursiv 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
```

## Avveiinger og forbehold

- **Cache-nøkkelstrategi**: `JSON.stringify` fungerer ikke for funksjoner, og nøkkelrekkefølge betyr noe for objekter. For objektargumenter unngår en `WeakMap` (nøkklet etter referanse) minnelekkasjer.
- **Ubegrenset vekst**: cachen krymper aldri — bruk en **LRU**-cache for langvarige prosesser.
- Memoizer kun når omberegning er genuint kostbar og input gjentas.

## Hvorfor det er viktig

Memoization er overalt: Reacts `useMemo`/`React.memo`, Reselect-selektorer, dynamisk programmering.

Konseptet (cache rene resultater etter input) er det samme; kunsten ligger i å velge nøkkelen og begrense cachen.

En generisk memoize-wrapper

Et klassisk eksempel: rekursiv Fibonacci

Avveiinger og forbehold

Hvorfor det er viktig

Relaterte spørsmål