Memoization

Dive tief in die aufregende Welt der Memoization ein, einer hochwirksamen Technik zur Optimierung von Algorithmen in der Informatik. Du wirst erfahren, was Memoization ist und wie es funktioniert. Des Weiteren wirst du das Prinzip und die praktische Bedeutung von Memoization verstehen, sowie seine Rolle in der Algorithmenentwicklung diskutieren. Schließlich erkundest du die Anwendung von Memoization in Javascript, inklusive eines praktischen Beispiels und fortgeschrittener Aspekte. Begib dich auf eine faszinierende Reise durch die Memoization und erweitere deine Kenntnisse in der Welt der Informatik.

Memoization in der Informatik: Definition

Prinzip der Memoization

function memoizeFunction(f) {
  var cache = {};
  return function() {
    var key = arguments[0];
    if (cache[key]) {
      return cache[key];
    } else {
      let val = f.apply(null, arguments);
      cache[key] = val;
      return val;
    }
  };
}

Praktische Bedeutung von Memoization

Memoization und Algorithmen: Funktion und Anwendung

Die Rolle von Memoization in der Algorithmenentwicklung

Die Nutzung von Memoization in der Algorithmenentwicklung ermöglicht es, ineffiziente Wiederholungen von Berechnungen zu vermeiden. Kritisch wird es meist bei rekursiven Algorithmen, da rekursive Algorithmen oft Subprobleme mehrmals mit identischen Eingaben bearbeiten. Handelsüblicherweis funktionieren Algorithmen, indem problematische Bereiche in kleinere Teilaufgaben unterteilt werden. Der Nachteil ist jedoch, dass viele dieser Teilaufgaben immer wieder vorkommen und von Neuem gelöst werden müssen.

Hier kommt die Technik der Memoization ins Spiel. Sie kann verhindern, dass Berechnungen durchgeführt werden, die bereits zuvor gelöst wurden. Um das Grundprinzip von Memoization besser zu erfassen, stellen wir uns einen Algorithmus wie einen Baum vor. Jeder Knoten stellt hierbei eine Teilaufgabe dar, die gelöst werden muss. Ohne Memoization würde jede Teilaufgabe jedes Mal erneut berechnet, wenn sie im Algorithmus auftritt. Mit Memoization hingegen wird das Ergebnis einer jeden Teilaufgabe gespeichert und bei wiederholtem Auftreten direkt aus dem Speicher, dem sogenannten Cache, ausgelesen.

function memoizedAlgorithm(input) {
  if (!cache[input]) {
    cache[input] = computeAlgorithm(input);
  }
  return cache[input];
}

Wie nutzt die Praxis Memoization bei Algorithmen?

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

function memoizedFibonacci(n, memo = {}) {
  if (n <= 1) return n;
  if (!memo[n]) {
    memo[n] = memoizedFibonacci(n - 1, memo) + memoizedFibonacci(n - 2, memo);   
  }
  return memo[n];
}

Einführung in die Memoization mit Javascript

Beispiel für Memoization in Javascript

function factorial(n) {
  if (n === 1) {
    return 1;
  }
  return n * factorial(n - 1);
}

Diese Funktion ist korrekt, hat jedoch eine signifikante Performance-Verzögerung, insbesondere bei größeren Eingabewerten. Der Grund für diese Verzögerung liegt in der wiederholten Berechnung derselben Fakultätswerte für jede rekursive Funktion. Hier kommt die Memoization ins Spiel. Durch Speichern und Wiederabrufen von bereits berechneten Fakultätswerten können wir die Berechnungszeit unserer Funktion spürbar verbessern.

let memo = {};
function memoizedFactorial(n) {
  if (memo[n]) {
    return memo[n];
  }
  if (n === 1) {
    return 1;
  }
  memo[n] = n * memoizedFactorial(n - 1);
  return memo[n];
}

Fortgeschrittene Aspekte von Memoization in Javascript

function memoize(fn) {
  let cache = {};
  return function(n) {
    if (cache[n] != undefined) return cache[n];
    else {
      let result = fn(n);
      cache[n] = result;
      return result;
    }
  };
}