Comment écrire du code de fonction de mémorisation simple en JavaScript ?-js tutoriel-php.cn

Comment écrire du code de fonction de mémorisation simple en JavaScript ?

PHPz

Libérer： 2023-08-25 08:17:02

avant

812 Les gens l'ont consulté

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

La mémoire est une technologie d'optimisation pour améliorer les performances des fonctions. Avant de commencer avec la technique de mémorisation, utilisons l'exemple suivant pour comprendre pourquoi nous en avons besoin.

Exemple (Un moyen facile de trouver les nombres de Fibonacci)

Dans l'exemple ci-dessous, nous avons implémenté une méthode simple pour trouver le nième nombre de Fibonacci. Nous utilisons une méthode récursive pour trouver le nième nombre de Fibonacci.

<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>

Copier après la connexion

L'exemple ci-dessus fonctionne bien pour les petites valeurs d'entrée inférieures à 1000, mais lorsque nous saisissons des valeurs d'entrée dans la plage 10⁴, cela prend plus de temps que d'habitude, et pour les entrées dans la plage 10⁶, Le navigateur plante en raison d'une mémoire hors limites.

Nous pouvons optimiser le code ci-dessus en utilisant la technologie de mémoire, qui nous permet de stocker les résultats des calculs précédents. Par exemple, pour trouver le 4ème nombre de Fibonacci, nous devons trouver les 3ème et 2ème nombres de Fibonacci. De même, pour trouver le troisième nombre de Fibonacci, il faut trouver le deuxième et le premier nombre de Fibonacci. Nous calculons donc ici deux fois le deuxième nombre de Fibonacci.

Maintenant, en supposant que vous souhaitiez trouver la nième plus grande valeur de la séquence de Fibonacci, vous pouvez réfléchir au nombre de fois où elle doit être répétée. Ainsi, à des fins d'optimisation, nous pouvons calculer le deuxième nombre de Fibonacci pour la première fois et le stocker dans une variable temporaire. Plus tard, lorsque nous aurons besoin de calculer à nouveau le deuxième nombre de Fibonacci, nous pourrons y accéder à partir du tableau, ce qui rendra le code plus efficace.

De plus, le stockage des résultats précédemment calculés dans un tableau pour une utilisation ultérieure est également une mémorisation.

Grammaire

Les utilisateurs peuvent suivre la syntaxe ci-dessous pour mémoriser le nième nombre de Fibonacci.

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

Copier après la connexion

Dans la syntaxe ci-dessus, nous vérifions d'abord si le nième nombre de Fibonacci existe déjà dans l'objet 'temp' puis renvoyons la valeur sinon, nous calculons sa valeur et ajoutons le minerai à l'objet temporaire.

Méthode

Étape 1 – Utilisez une instruction if pour vérifier si le résultat de n existe dans l'objet temporaire. Si tel est le cas, la valeur calculée précédemment est renvoyée.

Étape 2 – Si n est inférieur ou égal à 1, renvoyez 1 comme cas de base de la fonction récursive.

Étape 3 – Calculez les nombres de Fibonacci n-1 et n-2, ajoutez-les et stockez-les dans un objet temporaire pour une utilisation ultérieure.

Étape 4 – Stockez le nième numéro de Fibonacci et remettez-le à l'objet temporaire.

Exemple (trouver le nième nombre de Fibonacci en utilisant la mémoire)

À l'aide de techniques de mémorisation, nous avons optimisé le code pour le premier exemple de l'exemple ci-dessous. Nous utilisons l'objet temporaire pour stocker les résultats des calculs précédents. Dans le résultat, l'utilisateur peut constater que le code ci-dessous est plus efficace que le code du premier exemple.

<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>

Copier après la connexion

Méthode : utiliser la mémoire sans utiliser d'espace supplémentaire

Étape 1 – Initialisez a à 0 et b à 1.

Étape 2 – Utilisez une boucle for pendant n itérations pour trouver le nième nombre de Fibonacci.

Étape 3 – Ici, c est une variable temporaire qui stocke le (i-1)ème nombre de Fibonacci.

Étape 4 – Stockez la valeur de la variable b dans a.

Étape 5 – Stockez la valeur de la variable c dans la variable b.

Exemple

L'exemple ci-dessous est également une variante optimisée du premier exemple. Dans le deuxième exemple, nous avons utilisé un objet temporaire pour stocker les résultats du calcul précédent, mais dans le code ci-dessous, nous utilisons une seule variable temporaire nommée c.

Le code ci-dessous est le moyen le plus efficace de trouver la séquence de Fibonacci car sa complexité temporelle est O(n) et sa complexité spatiale est O(1).

<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>

Copier après la connexion

Dans ce didacticiel, nous avons découvert les techniques de mémoire permettant d'optimiser le code afin de le rendre plus efficace en termes de temps et d'espace. Les utilisateurs peuvent voir comment nous avons optimisé le code du premier exemple en utilisant différents algorithmes dans les deuxième et troisième exemples.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!