Implémentation de la mémorisation dans JavaScript

Points de base

• La mémorisation est une technique de programmation qui améliore les performances d'une fonction en mettant en cache les résultats des calculs précédents d'une fonction. Ceci est particulièrement utile pour les fonctions récursives et mathématiques qui utilisent souvent les mêmes paramètres.
• L'implémentation de la mémoire implique l'utilisation de caches indexées par les paramètres d'entrée par la fonction. Si le paramètre existe dans le cache, la valeur du cache est renvoyée; sinon, la fonction est exécutée et le résultat est ajouté au cache.
• Lorsque la mémorisation est utilisée pour les fonctions avec plusieurs paramètres, le cache multidimensionnel peut être utilisé, ou tous les paramètres peuvent être combinés pour former un seul index. Les paramètres de l'objet doivent être chaînés avant d'être utilisés comme index.
• La mémorisation a certaines limites. Il augmente la consommation de mémoire et peut ne pas être adapté aux fonctions qui s'exécutent rapidement ou appellent une basse fréquence. Il ne peut être automatisé qu'avec des références à des fonctions transparentes, c'est-à-dire que sa sortie dépend uniquement de son entrée et ne produit aucun effet secondaire.

Les programmes perdent souvent du temps à appeler des fonctions qui recalculent le même résultat à plusieurs reprises. Cela est particulièrement vrai pour les fonctions récursives et mathématiques. Le générateur de nombres Fibonacci est un exemple parfait. Une séquence Fibonacci est une série d'entiers commençant par zéro somme, où chaque valeur est la somme des deux premiers nombres de la séquence. Selon cette définition, les dix premiers numéros de Fibonacci sont: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34. Du point de vue de la programmation, les nombres de Fibonacci sont généralement calculés en utilisant les fonctions suivantes. Cette fonction fonctionne bien pour les valeurs "n" plus petites. Cependant, à mesure que "N" augmente, les performances baissent rapidement. En effet, les deux appels récursifs répètent le même travail. Par exemple, pour calculer le 50e numéro de Fibonacci, la fonction récursive doit être appelée plus de 40 milliards de fois (40 730 022 147 pour être exact)! Pour aggraver les choses, le calcul de la 51e figure nécessite de répéter le travail presque complètement deux fois. Si la fonction se souvient de ce qu'elle a calculé auparavant, elle peut atténuer le problème des travaux répétés.

function fibonacci(n) {
  if (n === 0 || n === 1)
    return n;
  else
    return fibonacci(n - 1) + fibonacci(n - 2);
}

Bases de la mémorisation

La mémorisation est une technique de programmation qui tente d'améliorer les performances d'une fonction en mettant en cache les résultats des calculs précédents d'une fonction. Parce que les objets JavaScript se comportent comme des tableaux associatifs, ils sont idéaux pour agir comme caches. Chaque fois que la fonction de mémoire est appelée, ses paramètres sont utilisés pour le cache d'index. Si les données existent, elles peuvent être renvoyées sans exécuter la fonction entière. Cependant, si les données ne sont pas mises en cache, la fonction est exécutée et le résultat est ajouté au cache.

Dans l'exemple suivant, la fonction Fibonacci d'origine est réécrite pour inclure la mémoire. Dans cet exemple, la fonction anonyme auto-exécutée renvoie une fonction interne f () qui est utilisée comme fonction Fibonacci. Lorsque f () est retourné, sa fermeture lui permet de continuer à accéder à l'objet "Mémo", qui stocke tous ses résultats précédents. Chaque fois que F () est exécuté, il vérifie d'abord si le résultat de la valeur "n" actuelle existe. S'il est présent, la valeur du cache est renvoyée. Sinon, exécutez le code Fibonacci d'origine. Notez que "Memo" est défini en dehors de f () afin qu'il puisse conserver sa valeur dans plusieurs appels de fonction. Rappelons que la fonction récursive d'origine a été appelée plus de 40 milliards de fois avant de pouvoir calculer le 50e numéro Fibonacci. En implémentant la mémoire, ce nombre tombe à 99.

function fibonacci(n) {
  if (n === 0 || n === 1)
    return n;
  else
    return fibonacci(n - 1) + fibonacci(n - 2);
}

Traitement des paramètres multiples

Dans l'exemple précédent, la fonction accepte un seul paramètre. Cela rend la mise en œuvre de la mise en cache assez simple. Malheureusement, la plupart des fonctions nécessitent plusieurs paramètres, ce qui complique les index mis en cache. Pour mémoriser une fonction avec plusieurs paramètres, le cache doit devenir multidimensionnel, ou tous les paramètres doivent être combinés pour former un seul indice.

Dans les méthodes multidimensionnelles, le cache devient la hiérarchie de l'objet, pas un seul objet. Chaque dimension est ensuite indexée par un seul paramètre. L'exemple suivant implémente un cache multidimensionnel pour la fonction Fibonacci. Dans cet exemple, la fonction accepte un paramètre supplémentaire "x" et il ne fait rien. Chaque fois qu'une fonction est appelée, le code vérifie si la dimension "x" existe et l'initialise si elle n'existe pas. Depuis lors, la dimension "x" est utilisée pour mettre en cache la valeur "n". Le résultat est que la fonction appelle Fibonacci ("Foo", 3) et Fibonacci ("bar", 3) ne sont pas considérées comme le même résultat.

var fibonacci = (function() {
  var memo = {};

  function f(n) {
    var value;

    if (n in memo) {
      value = memo[n];
    } else {
      if (n === 0 || n === 1)
        value = n;
      else
        value = f(n - 1) + f(n - 2);

      memo[n] = value;
    }

    return value;
  }

  return f;
})();

L'alternative au cache multidimensionnel est un seul objet de cache, qui est indexé par une combinaison de tous les paramètres de la fonction. Dans cette méthode, les paramètres sont convertis en un tableau puis utilisés pour le cache d'index. Chaque fonction a un objet intégré nommé "Arguments" qui contient les paramètres passés. "Arguments" est un objet de type appelé objet de classe de classe. Il est similaire à un tableau, mais ne peut pas être utilisé pour le cache d'index. Par conséquent, il doit d'abord être converti en tableau réel. Cela peut être fait à l'aide de la méthode Slice () du tableau. Le cache peut ensuite être indexé à l'aide de représentations de tableau, comme indiqué précédemment. L'exemple suivant montre comment y parvenir. Notez que la variable supplémentaire "tranche" est définie comme une référence à la méthode Slice () du tableau. En stockant cette référence, vous pouvez éviter les calculs répétés de la surcharge Array.prototype.slice (). Utilisez ensuite la méthode Call () pour appliquer Slice () aux "arguments".

var fibonacci = (function() {
  var memo = {};

  function f(x, n) {
    var value;

    memo[x] = memo[x] || {};

    if (x in memo && n in memo[x]) {
      value = memo[x][n];
    } else {
      if (n === 0 || n === 1)
        value = n;
      else
        value = f(x, n - 1) + f(x, n - 2);

      memo[x][n] = value;
    }

    return value;
  }

  return f;
})();

Paramètres d'objet de cache

Le schéma de mémoire introduit ici ne gère pas bien les paramètres de l'objet. Lorsque les objets sont utilisés comme index, ils sont d'abord convertis en représentations de chaînes, telles que "[objet objet]". Cela fait que plusieurs objets sont incorrectement mappés au même emplacement de cache. Ce comportement peut être corrigé en trafiquant les paramètres d'objet avant l'indexation. Malheureusement, cela ralentit également le processus de mémoire. L'exemple suivant crée une fonction de mémoire générale qui prend un objet comme argument. Notez que les paramètres d'objet sont stringifiés à l'aide de json.stringify () pour créer des index mis en cache.

function fibonacci(n) {
  if (n === 0 || n === 1)
    return n;
  else
    return fibonacci(n - 1) + fibonacci(n - 2);
}

Mémoire automatique

Dans tous les exemples précédents, la fonction est explicitement modifiée pour ajouter de la mémoire. L'infrastructure mémorisée peut également être implémentée sans modifier les fonctions du tout. Ceci est utile car il permet à la logique de fonction d'être implémentée séparément de la logique mémorisée. Cela se fait en créant une fonction utilitaire qui prend la fonction comme entrée et l'applique pour la mémoriser. La fonction Memoize () suivante prend la fonction "Func" comme entrée. Memoize () renvoie une nouvelle fonction qui enveloppe le mécanisme de cache autour de "Func". Notez que cette fonction ne gère pas les paramètres d'objet. Pour traiter l'objet, une boucle est nécessaire qui vérifiera chaque paramètre individuellement et Stringify selon les besoins.

var fibonacci = (function() {
  var memo = {};

  function f(n) {
    var value;

    if (n in memo) {
      value = memo[n];
    } else {
      if (n === 0 || n === 1)
        value = n;
      else
        value = f(n - 1) + f(n - 2);

      memo[n] = value;
    }

    return value;
  }

  return f;
})();

limitations

Lors de la réalisation de la mémoire, les points suivants doivent être rappelés. Premièrement, en stockant les anciens résultats, la fonction de mémorisation consomme une mémoire supplémentaire. Dans l'exemple de Fibonacci, la consommation de mémoire supplémentaire est illimitée. Si l'utilisation de la mémoire est un problème, un cache de taille fixe doit être utilisé. Les frais généraux associés à la mémoire peuvent également le rendre inadapté aux fonctions qui s'exécutent très rapidement ou ont une faible fréquence.

La plus grande limitation de la mémoire est qu'elle ne peut être appliquée automatiquement qu'aux fonctions

de référence transparente . Si la sortie d'une fonction ne dépend que de son entrée et ne produit aucun effet secondaire, la fonction est considérée comme un transparent de référence. Les appels qui font référence aux fonctions transparentes peuvent être remplacées par leur valeur de retour sans modifier la sémantique du programme. La fonction Fibonacci est référencée transparente car elle dépend entièrement de la valeur de "n". Dans l'exemple suivant, la fonction foo () n'est pas référencée transparente car elle utilise la variable globale "bar". Étant donné que "Bar" peut être modifié en dehors de FOO (), rien ne garantit que la valeur de retour restera inchangée pour chaque valeur d'entrée. Dans cet exemple, les deux appels à Foo () Retour des valeurs 2 et 3, même si les paramètres transmis aux deux appels sont les mêmes.

var fibonacci = (function() {
  var memo = {};

  function f(x, n) {
    var value;

    memo[x] = memo[x] || {};

    if (x in memo && n in memo[x]) {
      value = memo[x][n];
    } else {
      if (n === 0 || n === 1)
        value = n;
      else
        value = f(x, n - 1) + f(x, n - 2);

      memo[x][n] = value;
    }

    return value;
  }

  return f;
})();

choses à retenir

• La mémorisation peut potentiellement améliorer les performances en mettant en cache les résultats des appels de fonction précédents.
• La fonction de mémoire stocke un cache indexé par ses paramètres d'entrée. Si le paramètre existe dans le cache, la valeur du cache est renvoyée. Sinon, exécutez la fonction et ajoutez la valeur nouvellement calculée au cache.
• Les paramètres d'objet doivent être chaînés avant d'être utilisés comme index.
• La mémorisation peut être automatiquement appliquée aux fonctions transparentes de référence.
• La mémorisation peut ne pas être idéale pour les fonctions qui ne sont pas appelées fréquemment ou exécutées rapidement.

FAQ sur la mémorisation dans JavaScript (FAQ)

Quel est le but principal de l'utilisation de la mémoire en javascript?

La mémorisation est une technique de programmation utilisée pour optimiser les programmes informatiques en JavaScript et dans d'autres langages. Cette technique consiste à stocker les résultats des appels de fonction coûteux et à les réutiliser lorsque la même entrée réapparaît. Cela peut considérablement améliorer les performances du programme en évitant les calculs inutiles. Il est particulièrement utile dans les situations où des fonctions récursives ou des fonctions qui sont appelées à plusieurs reprises avec les mêmes paramètres.

Comment fonctionne la mémoire en JavaScript?

Dans JavaScript, la mémoire fonctionne en créant un cache pour stocker les résultats des appels de fonction. Lors de l'appel d'une fonction, la fonction vérifie d'abord si le résultat de l'entrée donnée est déjà en cache. Dans l'affirmative, la fonction renvoie le résultat mis en cache au lieu de réactualiser le calcul. Si le résultat n'est pas dans le cache, la fonction effectue le calcul, stocke le résultat dans le cache et renvoie le résultat.

Pouvez-vous fournir un exemple de fonction mémorisée en JavaScript?

Bien sûr, considérons un exemple d'une fonction simple qui calcule le factoriel de numérique. Sans mémoire, la fonction ressemble à ceci:

function fibonacci(n) {
  if (n === 0 || n === 1)
    return n;
  else
    return fibonacci(n - 1) + fibonacci(n - 2);
}

En utilisant la mémoire, nous pouvons optimiser cette fonction en stockant les résultats des appels de fonction précédents:

var fibonacci = (function() {
  var memo = {};

  function f(n) {
    var value;

    if (n in memo) {
      value = memo[n];
    } else {
      if (n === 0 || n === 1)
        value = n;
      else
        value = f(n - 1) + f(n - 2);

      memo[n] = value;
    }

    return value;
  }

  return f;
})();

Y a-t-il des limitations ou des inconvénients de l'utilisation de la mémoire en javascript?

Bien que la mémorisation puisse améliorer considérablement les performances des programmes JavaScript, il n'est pas sans ses limites. Un inconvénient majeur de la mémoire est qu'il peut consommer beaucoup de mémoire, en particulier lors du stockage de nombreuses données en cache. S'il n'est pas géré correctement, cela peut entraîner des problèmes de performance. De plus, la mémoire n'est valide que lorsque la fonction est appelée avec le même paramètre plusieurs fois. La mémorisation ne fournit aucun avantage de performance si l'entrée de la fonction est toujours différente.

Puis-je utiliser la mémorisation pour tous les types de fonctions en JavaScript?

La mémorisation est la plus efficace lorsqu'elle est utilisée avec des fonctions pures. Une fonction pure est une fonction qui renvoie toujours le même résultat de la même entrée et ne produit aucun effet secondaire. La mémorisation de la fonction peut conduire à des résultats inattendus s'il dépend d'un état externe ou a des effets secondaires. Ainsi, même si vous pouvez techniquement utiliser la mémorisation pour tout type de fonction en JavaScript, il est préférable pour les fonctions pures.

Comment mémoriser les fonctions avec plusieurs paramètres dans JavaScript?

La mise en œuvre de la mémoire pour une fonction avec plusieurs paramètres peut être un peu compliquée, mais cela est certainement possible. Une façon consiste à convertir les arguments en chaînes qui peuvent être utilisées comme clés dans le cache. Voici un exemple:

function fibonacci(n) {
  if (n === 0 || n === 1)
    return n;
  else
    return fibonacci(n - 1) + fibonacci(n - 2);
}

Y a-t-il une bibliothèque ou un outil qui peut aider à mémoriser en JavaScript?

Oui, il existe des bibliothèques et des outils qui peuvent aider à mémoriser en JavaScript. Par exemple, la populaire bibliothèque d'utilité JavaScript Lodash fournit une fonction _.memoize qui peut facilement mémoriser les fonctions. De même, la bibliothèque Ramda fournit une fonction R.memoizeWith qui vous permet de spécifier les fonctions de clé de cache personnalisées.

Comment effacer le cache dans la fonction de mémoire?

Le cache dans la fonction de mémoire peut être effacé en réinitialisant simplement l'objet de cache. Voici un exemple:

var fibonacci = (function() {
  var memo = {};

  function f(n) {
    var value;

    if (n in memo) {
      value = memo[n];
    } else {
      if (n === 0 || n === 1)
        value = n;
      else
        value = f(n - 1) + f(n - 2);

      memo[n] = value;
    }

    return value;
  }

  return f;
})();

La mémoire peut-elle être utilisée dans des frameworks JavaScript tels que React?

Oui, la mémoire est très utile dans les cadres JavaScript tels que React. Par exemple, React fournit une fonction React.memo qui peut être utilisée pour mémoriser des composants. Cela peut aider à améliorer les performances en empêchant le rediffusion inutilement des composants.

Comment est la mémoire en JavaScript par rapport aux autres techniques d'optimisation?

La mémorisation est une puissante technique d'optimisation, mais ce n'est pas toujours la meilleure solution. Dans certains cas, d'autres techniques d'optimisation telles que le désjitter et la limitation peuvent être plus appropriées. La clé est de comprendre les besoins et les contraintes spécifiques du programme et de choisir la bonne technologie d'optimisation.

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!