Comment résoudre le problème de mémoire insuffisante du tas JavaScript pour trouver des nombres premiers ?-js tutoriel-php.cn

Comment résoudre le problème de mémoire insuffisante du tas JavaScript pour trouver des nombres premiers ?

王林

Libérer： 2023-08-27 18:01:02

avant

1287 Les gens l'ont consulté

Comment résoudre le problème de mémoire insuffisante du tas JavaScript pour trouver des nombres premiers ?

Comme l'indique le message d'erreur « Out of Heap », cette erreur se produit lorsqu'un code JavaScript occupe plus de mémoire que celle allouée. Lorsque nous exécutons un programme JavaScript, l'ordinateur alloue une mémoire spécifique au programme JavaScript.

Lorsque nous exécutons du code en JavaScript ou dans n'importe quel langage de programmation, l'ordinateur crée un processus et alloue une quantité fixe de mémoire. Lorsqu'un programme a besoin de plus d'espace mémoire, il génère une erreur telle que mémoire insuffisante. Par exemple, si nous créons un tableau de taille 1020 et essayons d'initialiser chaque index de tableau avec une certaine valeur, le tas manquera de mémoire et générera une erreur.

Dans ce didacticiel, nous apprendrons comment résoudre le problème d'épuisement de la mémoire du tas JavaScript lors de la recherche de facteurs premiers d'un très grand ensemble de valeurs.

Les utilisateurs peuvent suivre l'exemple suivant pour visualiser les erreurs de débordement de tas.

Exemple (visualisation des erreurs)

Dans l'exemple ci-dessous, nous avons créé la fonction getPrimeFactors() qui renvoie les facteurs premiers de n'importe quel nombre. Quand on passe une petite valeur (proche de 10³) cela fonctionne parfaitement, mais quand on passe une grande valeur (proche de 10⁹) comme argument pour trouver les facteurs premiers cela donne une erreur, et la fenêtre du navigateur devient un écran noir.

Dans cet exemple, puisque nous avons utilisé deux boucles imbriquées pour parcourir le tableau, une erreur de mémoire se produit et la complexité temporelle du programme devient O(N²), ce qui est supérieur à la mémoire allouée.

<html>
<body>
   <h2>Visualizing the <i>Process out of memory</i> while finding all prime factors of a number in JavaScript </h2>
</body>
<script>
   try {
      function getPrimeFactors(num) {
         var factor = []; 
         let primes = [];
         for (let m = 2; m <= num; m++) {
            if (!factor[m]) {
               primes.push(m);
               for (let n = m << 1; n <= num; n += m) {
                  factor[n] = true;
               }
            }
         }
         return primes;
      }
      getPrimeFactors(1212121212323)
   } catch (err) {
      console.log(err.message)
   }
</script>
</html>

Copier après la connexion

Dans l'exemple de sortie ci-dessus, l'utilisateur peut observer une erreur de débordement de tas. Pour nous débarrasser de ce problème, nous devons optimiser la complexité temporelle et spatiale du code.

Ci-dessous, nous allons optimiser la complexité temporelle du code de l'exemple 1 pour trouver tous les facteurs premiers uniques d'un nombre donné.

Grammaire

Les utilisateurs peuvent écrire du code optimisé en suivant la syntaxe suivante pour trouver le facteur premier unique d'une valeur numérique donnée.

for (let m = 2; m * m <= value; m++) {
   if (value % m === 0) {
      
      // store factor to array
      while (value % m === 0) {
         value /= m;
      }
   }
}
if (value > 2) {
   
   // store factor to array
}

Copier après la connexion

Dans la syntaxe ci-dessus, nous utilisons une boucle for pour itérer jusqu'à ce que m*m soit inférieur à la valeur. Cela signifie que nous itérons jusqu'à ce que la racine carrée de la valeur soit supérieure à m.

Étapes

Étape 1 - Utilisez une boucle for pour itérer jusqu'à ce que la racine carrée de la valeur soit supérieure à m, où m est la variable d'initialisation de la boucle for.

Étape 2 - Dans la boucle for, si la valeur est divisible par m, alors cela signifie que m est un facteur premier de la valeur et la stocke dans le tableau des facteurs.

Étape 3 - Après cela, divisez la valeur par m et utilisez une boucle while pour diviser par m plusieurs fois si elle peut être divisée plusieurs fois. Ici, nous devons stocker des facteurs premiers uniques, nous ne stockons donc la valeur de m qu'une seule fois dans le tableau.

Étape 4 - Une fois toutes les itérations de la boucle for terminées, vérifiez si la valeur est supérieure à 2. Si tel est le cas, cela signifie que la valeur est le plus grand facteur premier et qu'elle est stockée dans le tableau.

Exemple (résolution des erreurs)

L'exemple ci-dessous utilise un tableau pour stocker les facteurs premiers. De plus, nous avons implémenté l’algorithme ci-dessus pour trouver des facteurs premiers.

Les utilisateurs peuvent essayer de trouver les facteurs premiers uniques de grandes valeurs (par exemple 1020) et voir si le code est capable de sortir sans aucune erreur.

<html>
<body>
   <h2>Solving the <i> Process out of memory </i> while finding all prime factors of a number in JavaScript</h2>
   <div id = "output"> </div>
</body>
<script>
   let output = document.getElementById('output');
   function getPrimeFactors(value) {
      let initial = value;
      var factors = [];
      for (let m = 2; m * m <= value; m++) {

         // if the value is divisible by m, it is a prime factor
         if (value % m === 0) {
            factors.push(m);

            // divide value by m until it is divisible
            while (value % m === 0) {
               value /= m;
            }
         }
      }

      // push largest prime factor at last
      if (value > 2) {
         factors.push(value); 
      }
      output.innerHTML += "The prime factors of " + initial + " are : " + factors + "<br/>";
   }
   getPrimeFactors(100000000002);
   getPrimeFactors(65416841658746141122);
</script>
</html>

Copier après la connexion

La traduction chinoise de

Exemple

est :

Exemple

Dans l'exemple ci-dessous, nous avons utilisé un ensemble pour stocker les facteurs premiers au lieu d'utiliser un tableau car nous devons obtenir les facteurs premiers uniques. De plus, nous avons utilisé une boucle for-of pour imprimer tous les facteurs premiers stockés dans l'ensemble.

<html>
<body>
   <h2>Solving the <i> Process out of memory </i> while finding all prime factors of a number in JavaScript</h2>
   <div id = "output"> </div>
</body>
<script>
   let output = document.getElementById('output');
   function getPrimeFactors(value) {
      let initial = value;
      var factors = new Set();
      for (let m = 2; m * m <= value; m++) {
         if (value % m === 0) {
            factors.add(m);
            while (value % m === 0) {
               value /= m;
            }
         }
      }
      if (value > 2) {
         factors.add(value);
      }
      output.innerHTML += "The prime factors of " + initial + " are : <br/>";

      // print values of a set
      for (let fac of factors) {
         output.innerHTML += fac + "<br/>";
      }
   }
   getPrimeFactors(44352747207453165);
</script>
</html>

Copier après la connexion

Nous avons appris à résoudre les erreurs de débordement de tas lors de la recherche de facteurs premiers d'un nombre. Chaque fois que nous rencontrons une erreur telle qu'un débordement de tas, nous devons optimiser notre code comme nous l'avons fait dans ce didacticiel.

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!