Memoization und Caching sind grundlegende Konzepte in der Programmierung.
Sie möchten Memoization verstehen, damit Sie Konzepte verstehen können, die auf Memoization aufbauen. Zum Beispiel die memo Higher-Order Component in React, useCallback und useMemo Hooks in React, Selektoren in Redux und vieles mehr.
In diesem Artikel und Video erhalten Sie einen detaillierten Einblick in Memoization mit Beispielen in JavaScript und TypeScript.
Memoization ist eine Methode, um die Performance zu steigern indem Berechnungen reduziert werden.
Wenn Sie ein Ergebnis zum ersten Mal berechnen, speichern Sie es. Wenn Sie das Ergebnis für dieselben Argumente erneut benötigen, verwenden Sie das gespeicherte Ergebnis, anstatt es neu zu berechnen.
Es gibt zwei Möglichkeiten, Memoization zu implementieren:
Implizites Caching liegt vor, wenn Sie die Caching-Logik manuell innerhalb von Funktionen implementieren.
Nehmen wir an, Sie haben eine einfache add -Funktion und möchten diese memoizieren.
function add(a, b) {
return a + b;
}Sie können diese add -Funktion umschreiben, sodass sie ihre Ergebnisse memoisiert.
Wenn Sie diesen Artikel mitprogrammieren möchten, initialisieren Sie ein neues npm-Projekt.
npm init --ySchreiben Sie dann eine Funktion namens memoizeAdd().
function memoizeAdd() {
const cache = {};
return function memoizedAdd(a, b) {
const key = `${a},${b}`;
if (key in cache) {
return cache[key];
} else {
const result = a + b;
cache[key] = result;
return result;
}
};
}
const memoizedAdd = memoizeAdd();
console.log(memoizedAdd(3, 4)); // Computes and caches the result.
console.log(memoizedAdd(3, 4)); // Retrieves the result from cache.
console.log(memoizedAdd(5, 6)); // Computes and caches a new result.
console.log(memoizedAdd(3, 4)); // Still retrieves the result from cache.
Lassen Sie uns aufschlüsseln, was hier passiert.
In memoizeAdd() erstellen Sie einen Cache, der typischerweise eine Hash-Tabelle oder ein Objekt ist, in dem Sie die Ergebnisse von Funktionsaufrufen speichern. Jeder Eintrag verwendet die Eingabe der Funktion als Schlüssel und die Ausgabe als Wert.
const cache = {
'3,1': 4,
'9001,2012': 11_013,
};
Als Nächstes geben Sie die memoizedAdd -Funktion zurück, die zwei Zahlen entgegennimmt a und b.
Jede eindeutige Kombination von Argumenten entspricht einem Schlüssel.
Bevor die Hauptlogik ausgeführt wird, prüft die Funktion den Cache, wobei die aktuelle Eingabe als Schlüssel verwendet wird. Ist die Eingabe im Cache vorhanden, gibt sie das zwischengespeicherte Ergebnis zurück.
Fehlt die Eingabe im Cache, berechnet die Funktion das Ergebnis, speichert es im Cache und gibt dann das Ergebnis zurück.
Wenn Sie die memoizedAdd Funktion aufrufen, wird das Ergebnis zusammen mit ihren Parametern gespeichert. Rufen Sie sie erneut mit denselben Parametern auf, kommt das Ergebnis aus dem Cache. Sind die Parameter neu, berechnet die Funktion das Ergebnis erneut.
Wenn Sie diesen Code ausführen, erhalten Sie die folgende Ausgabe.
$ node implicit-caching.js
7
7
11
7
In Sprachen, die Funktionen höherer Ordnung unterstützen, können Sie Dekoratoren verwenden, um Memoization hinzuzufügen, ohne die Kernlogik der Funktion zu ändern.
Funktionen höherer Ordnung sind Funktionen, die Funktionen als Argumente entgegennehmen und Funktionen zurückgeben.
Wenn dieses Konzept neu für Sie ist, möchten Sie vielleicht „Entfesseln Sie das Potenzial von JavaScript mit funktionaler Programmierung“lesen. Dieser Artikel erklärt Funktionen höherer Ordnung und vieles mehr von Grund auf.
Sehen Sie sich nun dieses einfache Beispiel einer Dekoratorfunktion für Memoization an.
function memoize(fn) {
const cache = new Map();
return function(...args) {
const key = JSON.stringify(args);
if (cache.has(key)) {
return cache.get(key);
}
const result = fn.apply(this, args);
cache.set(key, result);
return result;
};
}
function add(a, b) {
return a + b;
}
const memoizedAdd = memoize(add);
console.log(memoizedAdd(3, 4)); // Calculates and caches the result.
console.log(memoizedAdd(3, 4)); // Returns the cached result.
console.log(memoizedAdd(5, 6)); // Computes and caches a new result.
console.log(memoizedAdd(3, 4)); // Still retrieves the result from cache.
Gehen wir diesen Code ebenfalls Schritt für Schritt durch.
Zuerst erstellen Sie eine memoize Funktion, die eine andere Funktion, fn, als Argument entgegennimmt.
Es initialisiert zunächst einen Cache unter Verwendung einer Map. Dieser Cache speichert die Ergebnisse der Funktionsaufrufe. Eine Map wird anstelle eines Objekts verwendet, da sie eine größere Vielfalt an Schlüsseltypen verarbeiten kann.
const cache = new Map();
// Use numbers as key for cache.
map.set('[3,1]', 4);
// Use functions as key for cache.
map.set('[function increment(), function double()]', 42);
Die zurückgegebene Funktion akzeptiert eine beliebige Anzahl von Argumenten. Sie serialisiert diese Argumente in einen String, der als Schlüssel für den Cache verwendet wird.
Bevor die ursprüngliche Funktion ausgeführt wird, prüft der Wrapper, ob der Schlüssel bereits im Cache vorhanden ist. Ist dies der Fall, gibt die Funktion das zwischengespeicherte Ergebnis zurück.
Fehlt der Schlüssel im Cache, ruft der Wrapper die ursprüngliche Funktion auf, indem er fn.apply(this, args). Er speichert das Ergebnis im Cache und gibt es zurück.
Sie können jetzt Ihre add Funktion memoizen, indem Sie sie an die memoize Funktion übergeben.
Die memoizedAdd Funktion funktioniert genau wie im Beispiel für implizites Caching.
Und die Ausführung Ihres Codes liefert das gleiche Ergebnis.
$ node decorator-function.js
7
7
11
7
Die add Funktion ist rechnerisch günstig.
Um die Vorteile der Memoization zu nutzen, müssen Sie eine rechenintensive Funktion memoizieren.
Ein klassisches Beispiel ist die fibonacci Funktion. Abgesehen von der Memoization ist es nützlich, etwas über diese Funktion zu lernen, da sie ein häufiges Thema in Coding-Interviews ist.
Die Fibonacci-Folge ist eine Zahlenreihe, bei der jede Zahl die Summe der beiden vorhergehenden ist. Sie beginnt normalerweise mit 0 und 1. So beginnt sie:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
Mathematisch ausgedrückt lässt sich dies wie folgt darstellen:
So sieht die fibonacci Funktion in JavaScript aus.
function fibonacci(n) {
if (n <= 1) {
return n;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
Wenn n 0 oder 1 ist, gibt die Funktion zurück n direkt. Dies sind die ersten beiden Zahlen der Fibonacci-Folge.
Für Werte von n größer als 1 ruft sich die Funktion zweimal selbst auf: einmal für fibonacci(n - 1) und einmal für fibonacci(n - 2)und addiert die Ergebnisse dieser beiden Aufrufe.
Hier ist eine Tabelle, die zeigt, wie die Funktion fibonacci(4)berechnet:
Man kann sehen, dass fibonacci(2) zweimal berechnet wird, wenn fibonacci(4)aufgerufen wird: einmal direkt von fibonacci(4) und noch einmal von fibonacci(3).
Die negativen Auswirkungen dieser redundanten Berechnungen auf die Leistung verstärken sich, je größer die Eingabe für die Fibonacci -Funktion wird. Lesen Sie diesen Artikel bis zum Ende, um zu erfahren, wie Memoization diese Berechnung blitzschnell machen kann.
Bevor Sie Ihre Fibonacci -Funktion memoizieren, fügen Sie Ihrer memoisierten Funktion eine `name`-Eigenschaft hinzu. Dies erleichtert das Stack-Tracing, wenn Ihre Funktion einen Fehler auslöst.
function memoize(fn) {
const cache = new Map();
function memoizedFunction(...args) {
const key = JSON.stringify(args);
if (cache.has(key)) {
return cache.get(key);
}
const result = fn.apply(this, args);
cache.set(key, result);
return result;
}
Object.defineProperty(memoizedFunction, 'name', {
value: `memoized_${fn.name}`,
configurable: true
});
return memoizedFunction;
}
Verwenden Sie Object.defineProperty , um die `name` -Eigenschaft der `memoizedFunction` auf einen aussagekräftigeren Wert zu setzen, z. B. `memoized_${fn.name}`, wobei `fn.name` der Name der ursprünglichen Funktion ist. Indem Sie diese Eigenschaft als konfigurierbar festlegen, ermöglichen Sie bei Bedarf weitere Änderungen oder das Löschen der Eigenschaft.
Jetzt sind Sie bereit, die Auswirkungen der Memoization zu messen. Memoizieren Sie Ihre fibonacci Funktion und messen, wie lange es dauert, große Zahlen zu berechnen.
function memoize(fn) {
const cache = new Map();
function memoizedFunction(...args) {
const key = JSON.stringify(args);
if (cache.has(key)) {
return cache.get(key);
}
const result = fn.apply(this, args);
cache.set(key, result);
return result;
}
Object.defineProperty(memoizedFunction, 'name', {
value: `memoized_${fn.name}`,
configurable: true
});
return memoizedFunction;
}
function fibonacci(n) {
if (n <= 1) {
return n;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
const memoizedFibonacci = memoize(fibonacci);
function measurePerformance(func, arg) {
const startTime = process.hrtime.bigint();
const result = func(arg);
const endTime = process.hrtime.bigint();
// Convert nanoseconds to milliseconds.
const duration = (endTime - startTime) / BigInt(1000000);
console.log(`${func.name}(${arg}) = ${result}, Time: ${duration}ms`);
}
const n = 42;
console.log("Starting performance measurement:");
measurePerformance(fibonacci, n);
measurePerformance(memoizedFibonacci, n);
// Second call to show caching effect.
measurePerformance(memoizedFibonacci, n);
Die measurePerformance Funktion bewertet und meldet die Ausführungszeit einer gegebenen Funktion, indem sie Start- und Endzeiten mit process.hrtime.bigint(), die präzise Zeitstempel in Nanosekunden liefert. Nachdem die Funktion mit einem gegebenen Argument ausgeführt wurde, berechnet sie die Dauer in Millisekunden, indem sie die Startzeit von der Endzeit subtrahiert und das Ergebnis von Nanosekunden umrechnet. Anschließend protokolliert sie den Funktionsnamen, das Argument, die Ausgabe und die Ausführungsdauer in der Konsole.
Mithilfe von measurePerformancekönnen Sie die Leistung der Standard-Fibonacci-Funktion mit der memoisierten Version vergleichen.
Hier sind die Ergebnisse der Leistungsmessungen.
$ node fibonacci.js
Starting performance measurement:
fibonacci(42) = 267914296, Time: 2405ms
memoized_fibonacci(42) = 267914296, Time: 2394ms
memoized_fibonacci(42) = 267914296, Time: 0ms
Wie Sie sehen können, erfolgt die Ausführung der memoisierten Version beim zweiten Mal sofort, da das Ergebnis aus dem Cache abgerufen wird.
Wenn Sie Memoization verwenden, sollten Sie die .clear() Methode implementieren, um die Ressourcen und die Leistung Ihrer Anwendung zu verwalten. Dafür gibt es folgende Gründe:
Fügen Sie nun die Möglichkeit hinzu, den Cache zu leeren.
function memoize(fn) {
const cache = new Map();
function memoizedFunction(...args) {
const key = JSON.stringify(args);
if (cache.has(key)) {
return cache.get(key);
}
const result = fn.apply(this, args);
cache.set(key, result);
return result;
}
memoizedFunction.clear = function clear() {
cache.clear();
};
Object.defineProperty(memoizedFunction, 'name', {
value: `memoized_${fn.name}`,
configurable: true
});
return memoizedFunction;
}
function fibonacci(n) {
if (n <= 1) {
return n;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
const memoizedFibonacci = memoize(fibonacci);
function measurePerformance(func, arg) {
const startTime = process.hrtime.bigint();
const result = func(arg);
const endTime = process.hrtime.bigint();
// Convert nanoseconds to milliseconds.
const duration = (endTime - startTime) / BigInt(1000000);
console.log(`${func.name}(${arg}) = ${result}, Time: ${duration}ms`);
}
const n = 42;
// Measure memoized Fibonacci.
measurePerformance(memoizedFibonacci, n);
// Measure memoized Fibonacci second call.
measurePerformance(memoizedFibonacci, n);
// Clear cache and measure again.
console.log('Clearing cache and measuring again:');
memoizedFibonacci.clear();
measurePerformance(memoizedFibonacci, n);
Ändern Sie dann Ihr Anwendungsbeispiel so, dass es einen Aufruf der Methode .clear() enthält, nachdem das Ergebnis bereits erfolgreich memoisiert wurde.
$ node fibonacci.js
memoized_fibonacci(42) = 267914296, Time: 2456ms
memoized_fibonacci(42) = 267914296, Time: 0ms
Clearing cache and measuring again:
memoized_fibonacci(42) = 267914296, Time: 2484ms
Wie Sie sehen, führt das Leeren des Caches dazu, dass die Funktion ihr Ergebnis erneut berechnet.
Bisher wurde der gesamte Code in JavaScript geschrieben. Nun werden Sie die Codebeispiele in TypeScript übersetzen.
Installieren Sie TypeScript und die Node-Typen.
$ npm i --save-dev typescript @types/node
added 3 packages, and audited 4 packages in 1s
found 0 vulnerabilities
Initialisieren Sie dann ein neues TypeScript-Projekt.
$ npx tsc --init
Created a new tsconfig.json with:
TS
target: es2016
module: commonjs
strict: true
esModuleInterop: true
skipLibCheck: true
forceConsistentCasingInFileNames: true
You can learn more at <https://aka.ms/tsconfig>
Nun können Sie Ihre Memoize-Funktion in TypeScript schreiben.
type AnyFunction = (...args: any[]) => any;
interface MemoizedFunction<T extends AnyFunction> extends CallableFunction {
(...args: Parameters<T>): ReturnType<T>;
clear: () => void;
}
function memoize<T extends AnyFunction>(fn: T): MemoizedFunction<T> {
const cache = new Map<string, ReturnType<T>>();
const memoizedFunction = function(...args: Parameters<T>): ReturnType<T> {
const key = JSON.stringify(args);
if (cache.has(key)) {
return cache.get(key)!;
}
const result = fn(...args);
cache.set(key, result);
return result;
} as MemoizedFunction<T>;
memoizedFunction.clear = function clear() {
cache.clear();
};
Object.defineProperty(memoizedFunction, 'name', {
value: `memoized_${fn.name}`,
configurable: true
});
return memoizedFunction;
}
function fibonacci(n: number): number {
if (n <= 1) {
return n;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
const memoizedFibonacci = memoize(fibonacci);
function measurePerformance(func: MemoizedFunction<typeof fibonacci>, arg: number) {
const startTime = process.hrtime.bigint();
const result = func(arg);
const endTime = process.hrtime.bigint();
// Convert nanoseconds to milliseconds.
const duration = (endTime - startTime) / BigInt(1000000);
console.log(`${func.name}(${arg}) = ${result}, Time: ${duration}ms`);
}
const n = 42;
// Measure memoized Fibonacci.
measurePerformance(memoizedFibonacci, n);
// Measure memoized Fibonacci second call.
measurePerformance(memoizedFibonacci, n);
// Clear cache and measure again.
memoizedFibonacci.clear();
measurePerformance(memoizedFibonacci, n);
Hier erstellen Sie einen AnyFunction -Typ, der einen generischen Funktionstyp in TypeScript darstellt. Dieser Typ ist flexibel und ermöglicht jede Funktion, die eine beliebige Anzahl von Argumenten beliebigen Typs entgegennimmt und einen beliebigen Typ zurückgibt.
Als Nächstes definieren Sie ein generisches MemoizedFunction -Interface, das das integrierte CallableFunction Interface und führt eine clear Methode ein. Hierbei ist T ein generischer Typparameter, der auf jede Funktion beschränkt ist, die dem AnyFunction -Typ entspricht. Das Interface stellt sicher, dass Ihre memoized-Funktion sich wie die ursprüngliche Funktion verhält, indem sie dieselben Parameter akzeptiert und denselben Typ zurückgibt, und zusätzlich die clear -Methode verfügbar macht.
Sie können nun Ihre memoize-Funktion so implementieren, dass sie das MemoizedFunction Interface zurückgibt. Mithilfe des as -Schlüsselworts können Sie TypeScript mitteilen, dass die zurückgegebene Funktion eine MemoizedFunction.
Wenn Sie nun den Mauszeiger über memoizedFibonaccibewegen, kennt TypeScript den korrekten Typ der Funktion.
const memoizedFibonacci: MemoizedFunction<(n: number) => number>
Und TypeScript kennt auch die .clear()-Methode der memoisierten Funktion.
(property) MemoizedFunction<(n: number) => number>.clear: () => void
Ihre Funktion hat immer noch einen Mangel. Derzeit speichert die Memoization nur die Ergebnisse des vollständigen Funktionsaufrufs für jedes Argument, aber sie NICHT die Ergebnisse der rekursiven Zwischenaufrufe cachen.
Was ist ein potenzieller Nachteil der Verwendung von Rekursion ohne Memoization zur Lösung bestimmter Probleme?
Es ist der erhebliche Anstieg der Rechenzeit und des Ressourcenverbrauchs aufgrund redundanter Berechnungen.
Rufen Sie die Funktion mit einer großen Zahl n und dann mit n + 1auf.
// ... previous code stays the same.
const n = 42;
measurePerformance(memoizedFibonacci, n);
measurePerformance(memoizedFibonacci, n + 1);
Führen Sie dann Ihren Code aus, um den Leistungsunterschied zwischen 42 und 43 zu sehen.
$ npx tsx example-5.ts
memoized_fibonacci(42) = 267914296, Time: 2442ms
memoized_fibonacci(43) = 433494437, Time: 3975ms
Wie Sie sehen können, fibonacci(43) dauert viel länger, weil es fibonacci(42) von Grund auf neu berechnet, obwohl das Ergebnis bereits zwischengespeichert ist. Dasselbe Problem tritt bei jedem anderen rekursiven Zwischenaufruf auf.
Sie können dies beheben, indem Sie Memoization in der Implementierung der fibonacci Funktion.
// ... `memoize` is the same as above.
function fibonacci(n: number): number {
if (n <= 1) {
return n;
}
return memoizedFibonacci(n - 1) + memoizedFibonacci(n - 2);
}
const memoizedFibonacci = memoize(fibonacci);
function measurePerformance(func: MemoizedFunction<typeof fibonacci>, arg: number) {
const startTime = process.hrtime.bigint();
const result = func(arg);
const endTime = process.hrtime.bigint();
// Convert nanoseconds to milliseconds.
const duration = (endTime - startTime) / BigInt(1000000);
console.log(`${func.name}(${arg}) = ${result}, Time: ${duration}ms`);
}
const numbers = [10, 20, 30, 40, 42, 43, 500];
numbers.forEach(n => {
measurePerformance(memoizedFibonacci, n);
});
Wenn Sie die fibonacci Funktion definieren, verwenden Sie deren memoized-Version, um die nächste Zahl zu berechnen.
Führen Sie die Funktion nun mit verschiedenen großen Zahlen aus.
$ npx tsx fibonacci.ts
memoized_fibonacci(10) = 55, Time: 0ms
memoized_fibonacci(20) = 6765, Time: 0ms
memoized_fibonacci(30) = 832040, Time: 0ms
memoized_fibonacci(40) = 102334155, Time: 0ms
memoized_fibonacci(42) = 267914296, Time: 0ms
memoized_fibonacci(43) = 433494437, Time: 0ms
memoized_fibonacci(500) = 1.394232245616977e+104, Time: 0ms
Die Berechnung erfolgt nun bei jedem Funktionsaufruf praktisch sofort, egal wie groß die Eingabe ist.
Wenn Sie also memoizen, fragen Sie sich: „Was möchten Sie memoizen?“ Möchten Sie nur die äußere Funktion memoizen, oder möchten Sie auch Zwischenergebnisse in der Implementierung memoizen?
Wann sollten Sie Memoization verwenden?
Memoization ist nützlich bei:
Wie Sie gelernt haben, verbessert Memoization die Leistung, indem sie die Zeitkomplexität von Operationen reduziert und die Last auf Rechenressourcen durch die Vermeidung wiederholter Berechnungen verringert.
Doch Memoization birgt auch Nachteile.
Abonnieren Sie meinen YouTube-Kanal für weitere großartige JavaScript- und TypeScript-Tutorials!
.svg){kind=small}
