Was ist Memoisierung und warum ist sie wichtig?

Memoization ist eine Programmiertechnik, die die Leistung beschleunigt, indem die Rückgabewerte teurer Funktionsaufrufe zwischengespeichert werden. Eine “auswendig gelernte” Die Funktion gibt sofort einen vorberechneten Wert aus, wenn sie Eingaben hat, die sie zuvor gesehen hat.

Memoization ist eine spezielle Form des Cachings, die sich für Szenarien eignet, in denen eine kostspielige Funktion wiederholt ausgeführt wird, manchmal mit den gleichen Argumenten. Vorausgesetzt, dass die Funktion rein ist, so dass sie immer denselben Wert aus einem bestimmten Satz von Eingaben erzeugt, kann ihre Speicherung die Effizienz steigern und verschwendete CPU-Zyklen reduzieren.

Am häufigsten werden Sie in funktionalen Programmiersprachen auf Auswendiglernen stoßen. Die Technik hat jedoch einen breiten Nutzen. Es ist ein abstraktes Konzept, das Sie in jeden rekursiven Code integrieren können. Wir verwenden JavaScript für diesen Artikel, aber Sie könnten die Beispiele in Ihre Arbeitssprache umschreiben.

Ein einfaches Beispiel

Hier’ 8217;eine einfache Funktion, die die Fakultät einer gegebenen ganzen Zahl erzeugt:

const Fakultät = n => { wenn (n === 0) 1 zurückgeben; Sonst (factorial(n – 1) * n); };

Die faktorielle Berechnung ist rekursiv, da sich factorial() innerhalb der else-Bedingung selbst aufruft. Die Berechnung ist auch rein, da jeder gegebene Wert von n immer den gleichen Wert zurückgibt. factorial(5) ist 120, unabhängig vom Status des Programms.

Aufgrund der rekursiven Natur der Funktion führt die Berechnung der Fakultät mehrerer großer Zahlen zu verschwendeten Operationen:

const x = Fakultät(100); const y = Fakultät(50);

Alle Berechnungen zur Berechnung von y wurden bereits im Rahmen der Berechnung von x durchgeführt. Wenn Factorial() seine Eingaben und ihre entsprechenden Ausgaben zwischenspeichern würde, könnte die Berechnung von y erheblich beschleunigt werden.

Auswendiglernen der Fakultätsfunktion

Hier ein grundlegender Ansatz, der die Funktion factorial() auswendig lernt:

const cache = &#123 ;}; konstant Fakultät = n => { wenn (Cache[n]) { Rückgabecache[n]; } lassen Wert; wenn (n === 0) Wert = 1; else Wert = (faktoriell(n – 1) * n); Cache[n] = Wert; Rückgabewert; };

Jetzt gibt es ein Cache-Objekt, das Factorial() verwendet, um seine Ausgabewerte aufzuzeichnen. Jedes Mal, wenn die Funktion aufgerufen wird, prüft sie zuerst, ob sie zuvor die Eingabe n gesehen hat. Wenn ja, kann es sofort kurzschließen und den zwischengespeicherten Wert zurückgeben. Andernfalls wird die rekursive Berechnung normal fortgesetzt, aber nachfolgende Durchläufe mit derselben Zahl werden beschleunigt.

Nun wird die Berechnung von factorial(50) nach factorial(100) wesentlich effizienter sein. Die Fakultät von 50 würde als Teil der Fakultät von 100 berechnet, sodass die Funktion den Wert fast sofort zurückgeben könnte.

Eine allgemeinere Lösung

Der obige Code funktioniert zwar, ist aber spezifisch für die Funktion factorial(). Wenn Sie andere ähnliche Funktionen verwenden, müssen Sie den Caching-Code manuell zu jedem hinzufügen.

Eine allgemeinere Lösung lässt Sie jede Funktion mit einer Funktion höherer Ordnung umschließen, die die Merkfähigkeit:

const memoize = fn => { const cache = {}; (…Args) => { const argsString = JSON.stringify(args); wenn (!cache[argsString]) { Cache[argsString] = fn(…args); } Rückgabecache[argsString]; } };

Jetzt können Sie die ursprüngliche Funktion factorial() anpassen:

const factorial = memoize(n => { wenn (n === 0) 1 zurückgeben; Sonst (factorial(n – 1) * n); }); Werbung

Durch Umschließen von factorial() mit memoize() erhält es automatische Memoisierungsfunktionen. Die Wrapper-Funktion gibt eine neue Funktion zurück, die alle Aufrufe von factorial() abfängt, ihre Argumente stringifiziert und überprüft, ob sie schon einmal gesehen wurden. Wenn ja, wird der vorherige Rückgabewert wiederverwendet, ohne die reale Funktion überhaupt aufzurufen. Wenn neue Argumente angezeigt werden, wird die Funktion aufgerufen und ihre Ausgabe wird dem Cache hinzugefügt.

Der Wrapper verwendet die JavaScript-Rest-Parameter-Syntax, um eine variadische Anzahl von Argumenten zu akzeptieren. Dies bedeutet, dass es mit jeder JavaScript-Funktion funktioniert. Dieser Ansatz verwendet JSON.stringify(), um die Zeichenfolgendarstellung der Argumente zu erstellen. Seien Sie also vorsichtig, wenn Sie eine Funktion mit komplexen Objekten aufrufen, die nicht vollständig als JSON dargestellt werden können.

Wann sollte Memoization nicht verwendet werden?

Die Memoisierung kann zu erheblichen Leistungsverbesserungen führen, insbesondere bei mathematisch schweren Operationen. Es ist jedoch keine Technik, die überall verwendet werden kann. Nicht alle Funktionen sollten auswendig gelernt werden, da dies in einigen Fällen die Leistung beeinträchtigen könnte.

Indem Sie eine Funktion mit memoize() umschließen, erzwingen Sie bei jeder Funktion einen Vergleich der Eingabeargumente wird genannt. Dies allein wird einige CPU-Zeit verbrauchen. Der obige Beispiel-Wrapper führt JSON.stringify() jedes Mal aus, wenn die Funktion aufgerufen wird, wodurch ein neuer Overhead hinzugefügt wird.

Die Speicherung eignet sich für Funktionen, bei denen eine hohe Wahrscheinlichkeit besteht, dass regelmäßig dieselben Eingabewerte angezeigt werden. Wenn Sie selten eine Funktion mit denselben Argumenten aufrufen, sind Cache-Treffer selten und Sie verlieren möglicherweise Leistung durch die Serialisierung und den Vergleich von Argumenten. Die Pflege des Caches erhöht auch die Speichernutzung, da alle vorherigen Ein- und Ausgaben beibehalten werden müssen.

Sie sollten daher die Rolle jeder Funktion in Ihrem Programm vollständig prüfen, bevor Sie sich für das Auswendiglernen entscheiden. Vergleichen Sie die Leistung mit und ohne Memoisierung. Manchmal kann es vorteilhafter sein, sich auf die eigenen Optimierungen des Browsers zu verlassen.

Denken Sie zum Schluss daran, dass einige Funktionen nicht auswendig gelernt werden können. Die Technik funktioniert nur mit reinen Funktionen—wenn Ihre Funktion globale Variablen oder einen anderen Anwendungszustand erreicht, sollte sie nicht auswendig gelernt werden!

const functionUsingGlobalState = n => { if (n === window.scrollY) true zurückgeben; else return functionUsingGlobalState(n – 1); }

Das Auswendiglernen der obigen Funktion kann nach dem ersten Durchlauf zu unerwarteten Ergebnissen führen. Werte von n werden unter Verwendung der ursprünglichen window.scrollY-Version zwischengespeichert. Der Memoization-Wrapper gibt die zwischengespeicherte Ausgabe zurück, auch wenn sich window.scrollY geändert hat.

Zusammenfassung

Memoization ist eine Form des Cachings, die die Leistung von sich wiederholenden rekursiven Operationen. Es handelt sich um eine funktionale Programmiertechnik, die als generischer Wrapper für jede reine Funktion implementiert werden kann.

Memoisierung wird am häufigsten in häufig aufgerufenen Funktionen auftreten, die rechenintensive Operationen ausführen. Es hilft, Verschwendung zu vermeiden, indem es die Notwendigkeit beseitigt, Werte neu zu berechnen, die bereits als Teil eines vorherigen Aufrufs erzeugt wurden.

Die Vorteile der Memoisierung werden bei Funktionen, die einfach zu beginnen oder selten aufgerufen werden, weniger offensichtlich. In einigen Fällen kann die unsachgemäße Verwendung der Memoisierung tatsächlich die Leistung beeinträchtigen, also merken Sie sich nicht blind jede Funktion in Ihrer Anwendung.