suchen

Heim >Web-Frontend >js-Tutorial >Wie schreibe ich einfachen Memoization-Funktionscode in JavaScript?

Wie schreibe ich einfachen Memoization-Funktionscode in JavaScript?

PHPz
PHPznach vorne
2023-08-25 08:17:02873Durchsuche

如何用 JavaScript 编写简单的 Memoization 函数代码？

Speicher ist eine Optimierungstechnologie zur Verbesserung der Funktionsleistung. Bevor wir mit der Auswendiglerntechnik beginnen, wollen wir anhand des folgenden Beispiels verstehen, warum wir sie benötigen.

Beispiel (Einfache Möglichkeit, Fibonacci-Zahlen zu finden)

Im folgenden Beispiel haben wir eine einfache Methode implementiert, um die n-te Fibonacci-Zahl zu ermitteln. Wir verwenden eine rekursive Methode, um die n-te Fibonacci-Zahl zu ermitteln. 

<html>
<body>
   <h3>Finding the nth Fibonacci using recursive approach number in JavaScript</h3>
   <p>Enter the number to find the nth Fibonacci number.</p>
   <input type = "number" id = "fib"> <br>
   <div id = "content"> </div> <br>
   <button onclick = "executeFunc()"> Submit </button>
   <script>
      let content = document.getElementById('content');
      
      // function to write the fibonacci series
      function findFib(n) {
         if (n <= 1) return n;
         return findFib(n - 1) + findFib(n - 2);
      }
      function executeFunc() {
         let n = document.getElementById('fib').value;
         content.innerHTML = "The " + n + "th fibonacci number is " + findFib(n);
      } 
   </script>
</body>
</html>

Das obige Beispiel funktioniert gut für kleine Eingabewerte unter 1000, aber wenn wir Eingabewerte im Bereich 104 eingeben, dauert es länger als gewöhnlich, und für Eingaben im Bereich 106 Der Browser stürzt aufgrund von Speicherüberschreitung ab.

Wir können den obigen Code mithilfe der Speichertechnologie optimieren, die es uns ermöglicht, die Ergebnisse früherer Berechnungen zu speichern. Um beispielsweise die 4. Fibonacci-Zahl zu finden, müssen wir die 3. und 2. Fibonacci-Zahl finden. Um die dritte Fibonacci-Zahl zu finden, müssen wir ebenfalls die zweite und erste Fibonacci-Zahl finden. Hier berechnen wir also die zweite Fibonacci-Zahl zweimal.

Angenommen, Sie möchten den n-tgrößten Wert der Fibonacci-Folge ermitteln, können Sie darüber nachdenken, wie oft er wiederholt werden muss. Zu Optimierungszwecken können wir also erstmals die zweite Fibonacci-Zahl berechnen und in einer temporären Variablen speichern. Wenn wir später die zweite Fibonacci-Zahl erneut berechnen müssen, können wir über das Array darauf zugreifen, wodurch der Code effizienter wird.

Auch das Speichern zuvor berechneter Ergebnisse in einem Array zur späteren Verwendung ist eine Memorisierung.

Grammatik

Benutzer können der folgenden Syntax folgen, um sich die n-te Fibonacci-Zahl zu merken. 

if (temp[n]) return temp[n];
if (n <= 1) return n;
return temp[n] = findFib(n - 1, temp) + findFib(n - 2, temp);

In der obigen Syntax prüfen wir zunächst, ob die n-te Fibonacci-Zahl bereits im „temp“-Objekt vorhanden ist, und geben dann den Wert zurück. Andernfalls berechnen wir ihren Wert und addieren das Erz zum temporären Objekt.

Methode

Schritt 1 – Verwenden Sie eine if-Anweisung, um zu prüfen, ob das Ergebnis von n im temporären Objekt vorhanden ist. Wenn ja, wird der zuvor berechnete Wert zurückgegeben.

Schritt 2 – Wenn n kleiner oder gleich 1 ist, geben Sie 1 als Basisfall der rekursiven Funktion zurück.

Schritt 3 – Berechnen Sie die Fibonacci-Zahlen n-1 und n-2, addieren Sie sie und speichern Sie sie zur späteren Verwendung in einem temporären Objekt.

Schritt 4 – Speichern Sie die n-te Fibonacci-Zahl und geben Sie sie an das temporäre Objekt zurück.

Beispiel (Finden der n-ten Fibonacci-Zahl mithilfe des Gedächtnisses)

Mithilfe von Memoisierungstechniken haben wir den Code für das erste Beispiel im folgenden Beispiel optimiert. Wir verwenden das temporäre Objekt, um die Ergebnisse früherer Berechnungen zu speichern. In der Ausgabe kann der Benutzer erkennen, dass der folgende Code effizienter ist als der Code im ersten Beispiel. 

<html>
<body>
   <h3>Finding the nth Fibonacci number using memoization using extra space in JavaScript</h3>
   <p>Enter the number to find the nth Fibonacci number.</p>
   <input type = "number" id = "fib"> <br>
   <div id = "content"> </div> <br>
   <button onclick = "start()"> Submit </button>
   <script>
      let content = document.getElementById('content');
      function findFib(n, temp) {
         if (temp[n]) return temp[n];
         if (n <= 1) return n;
         return temp[n] = findFib(n - 1, temp) + findFib(n - 2, temp);
      } 
      function start() {
         let n = document.getElementById('fib').value;
         content.innerHTML = "The " + n + "th fibonacci number using memoization is " + findFib(n, {}) + "<br>";
      }
   </script>
</body>
</html>

Methode: Speicher nutzen, ohne zusätzlichen Speicherplatz zu verbrauchen

Schritt 1 – Initialisieren Sie a auf 0 und b auf 1.

Schritt 2 – Verwenden Sie eine for-Schleife für n Iterationen, um die n-te Fibonacci-Zahl zu finden.

Schritt 3 – Hier ist c eine temporäre Variable, die die (i-1)-te Fibonacci-Zahl speichert.

Schritt 4 – Speichern Sie den Wert der b-Variablen in a.

Schritt 5 – Speichern Sie den Wert der Variablen c in Variable b.

Beispiel

Das folgende Beispiel ist ebenfalls eine optimierte Variante des ersten Beispiels. Im zweiten Beispiel haben wir ein temporäres Objekt verwendet, um die Ergebnisse der vorherigen Berechnung zu speichern, aber im folgenden Code verwenden wir eine einzelne temporäre Variable namens c.

Der folgende Code ist der effizienteste Weg, die Fibonacci-Folge zu finden, da ihre zeitliche Komplexität O(n) und ihre räumliche Komplexität O(1) beträgt. 

<html>
<body>
   <h3>Finding the nth Fibonacci number using memoization in JavaScript</h3>
   <p>Enter the number to find the nth Fibonacci number:</p>
   <input type = "number" id = "fib"> <br>
   <div id = "content"> </div> <br>
   <button onclick = "findFib()"> Submit </button>
   <script>
      let content = document.getElementById('content');
      
      // function to write the fibonacci series
      function findFib() {
         let n = document.getElementById('fib').value;
         let a = 0, b = 1, c;
         if (n == 0) {
            return a;
         }
         for (let i = 2; i <= n; i++) {
            c = a + b;
            a = b;
            b = c;
         }
         content.innerHTML += "The " + n + "th Fibonacci number using memoization is " + b;
      }
   </script>
</body>
</html>

In diesem Tutorial haben wir Speichertechniken zur Optimierung von Code kennengelernt, um ihn zeit- und platzsparender zu gestalten. Im zweiten und dritten Beispiel können Sie sehen, wie wir den Code des ersten Beispiels mithilfe verschiedener Algorithmen optimiert haben.

Das obige ist der detaillierte Inhalt vonWie schreibe ich einfachen Memoization-Funktionscode in JavaScript?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

Stellungnahme：
Dieser Artikel ist reproduziert unter:tutorialspoint.com. Bei Verstößen wenden Sie sich bitte an admin@php.cn löschen
Vorheriger Artikel：decipher.update()-Methode in Node.jsNächster Artikel：decipher.update()-Methode in Node.js

In Verbindung stehende Artikel

Mehr sehen