Was ist Memoisierung?

Memoisierung ist eine Optimierungstechnik, die in der Programmierung verwendet wird, um die Ausführung von Funktionen zu beschleunigen, indem die Ergebnisse ihrer Aufrufe mit bestimmten Eingabewerten zwischengespeichert werden.

Beim späteren Aufruf der Funktion mit denselben Argumenten wie zuvor, berechnet die Funktion das Ergebnis nicht erneut, sondern gibt den gespeicherten Wert aus dem Cache zurück.

Dies ist besonders effektiv für ressourcenintensive Funktionen mit deterministischem Verhalten (Funktionen, die immer dasselbe Ergebnis für dieselben Eingabedaten liefern).

Vorteile:

• Beschleunigung ressourcenintensiver Funktionen.
• Verringerung der CPU-Belastung durch Vermeidung wiederholter Berechnungen.

Nachteile:

• Erhöhter Speicherverbrauch für die Cache-Speicherung.
• Kann ineffizient sein für Funktionen, die häufig mit unterschiedlichen Argumenten aufgerufen werden oder ihr Verhalten ändern.

Beispiel in JavaScript:

function fibonacci(n) { // Funktionale Definition der Fibonacci-Zahlen
  if (n <= 1) {
    return n;
  }
  return fibonacci(n - 1) + fibonacci(n - 2); // Rekursiver Aufruf
}

// Memoisierte Version der Fibonacci-Funktion
function memoizedFibonacci(n, cache = {}) {
  if (n in cache) { // Prüfen, ob das Ergebnis im Cache ist
    return cache[n];
  }

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

  // Ergebnis berechnen und im Cache speichern
  cache[n] = memoizedFibonacci(n - 1, cache) + memoizedFibonacci(n - 2, cache);
  return cache[n];
}

// Geschwindigkeitsvergleich:
console.time('Ohne Memoisierung');
fibonacci(40);
console.timeEnd('Ohne Memoisierung'); // Deutlich längere Zeit

console.time('Mit Memoisierung');
memoizedFibonacci(40);
console.timeEnd('Mit Memoisierung'); // Deutlich kürzere Zeit

In diesem Beispiel berechnet die Funktion fibonacci ohne Memoisierung die gleichen Werte mehrfach. Die memoized-Version memoizedFibonacci speichert die berechneten Werte im Objekt cache, was die nachfolgenden Aufrufe mit denselben Argumenten erheblich beschleunigt.