Memoization in JavaScript, über useMemo hinaus

Memoization cacht das Ergebnis von an Funktionsaufruf, abgelegt nach seinen Argumenten, sodass a erneuter Aufruf mit denselben Argumenten den gecachten Wert zruckgibt, statt die Orbeit nochamoi zu machn. De meisten JavaScript-Entwickler lernen's über Reacts useMemo kennen, aber des is nur a enge Anwendung vo ana allgemeinen Technik, de genauso nützlich is in normalen Funktionen, rekursiven Algorithmen und serverseitigem Code, der nix mit Rendering zum tun hot.

Des Kernmuster

Memoization braucht drei Sochn: a Möglichkeit, aus den Argumenten an Cache-Key abzuleiten, an Speicher für die gecachten Ergebnisse, und an Wrapper, der den Speicher prüft, bevor er die echte Funktion aufruaft.

function memoize(fn, keyFn = (...args) => JSON.stringify(args)) {
  const cache = new Map();

  return function memoized(...args) {
    const key = keyFn(...args);
    if (cache.has(key)) {
      return cache.get(key);
    }
    const result = fn.apply(this, args);
    cache.set(key, result);
    return result;
  };
}

function expensiveCalculation(n) {
  console.log(`Computing for ${n}...`);
  let total = 0;
  for (let i = 0; i < n * 1e7; i++) total += i;
  return total;
}

const memoized = memoize(expensiveCalculation);

memoized(5); // Computing for 5... (slow)
memoized(5); // instant, no log line — served from cache
memoized(6); // Computing for 6... (slow, different key)

Die Standard-Key-Funktion mit JSON.stringify funktioniert für primitive und einfache Objekt-Argumente, bricht aber bei Funktionen, Map-/Set-Argumenten oda Objekten zam, wo die Key-Reihenfolge ned garantiert stabil is - gib an eigenen keyFn mit, wenn der Standard ned reicht.

Warum des über React hinaus zählt

useMemo gibt's, um zum vermeiden, an Wert bei jedem Render von ana Komponente neu zu berechnen. Des is a echter Anwendungsfall, aber Memoization is genauso wertvoll überall, wo a Funktion:

• Pur is (gleicher Input liefert imma gleichen Output), und
• Teuer im Vergleich zu ana Cache-Abfrage (a Datenbankabfrage, a Regex gegn an riesigen String, a rekursive Berechnung).

Nix davon braucht React. Ein Node.js-API-Handler, der denselben aggregierten Bericht für jeden Request in ana Serie neu berechnet, a CLI-Tool, des in ana Charge pro Aufruf dieselbe Config-Datei neu parst, oda a rekursiver Algorithmus, der immer wieda dasselbe Teilproblem neu berechnet, sand olle gute Kandidaten.

Der Klassiker: Rekursives Fibonacci

Naives rekursives Fibonacci is das Lehrbuchbeispiel, weil der Performance-Unterschied dramatisch und leicht zum Sehen is.

function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

fib(35) mocht ungefähr 30 Millionen Aufrufe, die meisten davon berechnen dieselben Werte neu - fib(10) wird tausende Moi ois Teilproblem von fib(35) ausgrechnet. Memoization reduziert des auf oan Aufruf pro verschiedenem n:

function memoizedFib() {
  const cache = new Map([[0, 0], [1, 1]]);

  function fib(n) {
    if (cache.has(n)) return cache.get(n);
    const result = fib(n - 1) + fib(n - 2);
    cache.set(n, result);
    return result;
  }

  return fib;
}

const fib = memoizedFib();
fib(35); // 30 million calls collapse to 36

Des is Memoization auf Rekursion angwendet, manchmoi "Top-Down Dynamic Programming" gnannt - dieselbe Idee wia der generische memoize()-Wrapper, nur händisch innerhoib vo da rekursiven Funktion angwendet, sodass jeder Aufruf den Cache prüft, bevor er weiter rekursiert.

Cache-Wachstum is der Kompromiss, ka Fußnote

A unbegrenzter Map-Cache is a Speicherleck, des drauf wartet zum passiern, wenn die Funktion über die Lebensdauer von da App mit vüle verschiedenen Argumenten aufgrufn wird - a memoisierter Pro-Request-Handler in am langlaufenden Server is a klassischer Weg, langsam unbegrenzten Speicher aufzubaun. Begrenz den Cache mit ana LRU-Verdrängungsstrategie (least-recently-used), sobois des a echtes Risiko is:

function memoizeWithLimit(fn, maxSize = 100) {
  const cache = new Map();

  return function memoized(...args) {
    const key = JSON.stringify(args);
    if (cache.has(key)) {
      const value = cache.get(key);
      cache.delete(key);
      cache.set(key, value); // move to "most recently used" position
      return value;
    }

    const result = fn.apply(this, args);
    cache.set(key, result);

    if (cache.size > maxSize) {
      const oldestKey = cache.keys().next().value; // Map preserves insertion order
      cache.delete(oldestKey);
    }

    return result;
  };
}

Map iteriert in Einfügereihenfolge, und an Key beim Zugriff neu einzufügen (löschen, dann setzen) schiabt ihn ans Ende - des reicht, um LRU-Verdrängung ohne separate verkettete Liste zu implementiern.

Warum useMemo ned "Memoization, aber für React" is

useMemo(() => computeThing(a, b), [a, b]) schaut wia des generische Muster aus, hot aber React-spezifische Semantik, de ma kennen soit:

• Da Cache hoit genau oan Eintrag - das letzte Dependency-Array. Es is koa Map mit jedem jemois gsehnen Input als Key; a neiches Dependency-Array verdrängt das vorherige Ergebnis komplett.
• React darf den memoisierten Wert ausdrücklich verwerfn und trotzdem neu berechnen (wegen Speicherdruck), also is useMemo a Performance-Hinweis, ka Korrektheitsgarantie - verlass di nie drauf für Seiteneffekte oda um zu vermeiden, wos mit beobachtbaren Effekten nochamoi zum laufn.
• Es existiert nur für die Lebensdauer von da Komponenteninstanz.

A generisches memoize() mit Map-Cache hot koane dieser Einschränkungen und koane dieser Sicherheitsgeländer - und genau deswegn is es des falsche Werkzeug in ana Komponente (unbegrenztes Wachstum über Renders hinweg) und des richtige für a eigenständige reine Funktion.

Wann ma ned memoisiert

Memoization tauscht Speicher gegn CPU-Zeit. Es passt schlecht, wenn die Funktion schon von Haus aus billig is (die Cache-Abfrage kann mehr kostn ois einfach neu zu berechnen), wenn Argumente selten wiederholt wern (a Cache, der nie getroffen wird, is reiner Overhead), oda wenn die Funktion eigentlich ned pur is (was zum memoisiern, des von veränderlichem externem State abhängt, liefert fröhlich veraltete, falsche Antworten). Profil, bevor du dazu greifst - Memoization behebt an gmessenen Hotspot, es is ka Default, den ma über jede Funktion streut.