JavaScript Utiliser un mémoizer pour les fonctions de calcul intensif


Exemple

Si vous créez une fonction qui peut être lourde sur le processeur (client ou serveur), vous pouvez envisager un mémoizer qui est un cache des exécutions de fonctions précédentes et de leurs valeurs renvoyées . Cela vous permet de vérifier si les paramètres d'une fonction ont été passés auparavant. Rappelez-vous, les fonctions pures sont celles qui donnent une entrée, renvoient une sortie unique correspondante et ne provoquent pas d'effets secondaires hors de leur portée. Vous ne devez donc pas ajouter de mémoizer à des fonctions imprévisibles ou dépendantes de ressources externes valeurs retournées).

Disons que j'ai une fonction factorielle récursive:

function fact(num) {
  return (num === 0)? 1 : num * fact(num - 1);
}

Si je passe de petites valeurs de 1 à 100 par exemple, il n'y aurait pas de problème, mais une fois que nous commencerons à aller plus loin, nous pourrions faire exploser la pile d'appels ou rendre le processus un peu pénible pour le moteur Javascript dans lequel nous le faisons. en particulier si le moteur ne compte pas avec l’optimisation de l’appel (bien que Douglas Crockford affirme que l’optimisation de l’appel est incluse dans l’ES6 natif).

Nous pourrions coder dur notre propre dictionnaire de 1 à dieu-sait-quel nombre avec leurs factorielles correspondantes mais, je ne suis pas sûr si je le conseille! Créons un mémoizer, allons-nous?

var fact = (function() {
  var cache = {}; // Initialise a memory cache object
  
  // Use and return this function to check if val is cached
  function checkCache(val) {
    if (val in cache) {
      console.log('It was in the cache :D');
      return cache[val]; // return cached
    } else {
      cache[val] = factorial(val); // we cache it
      return cache[val]; // and then return it
    }
    
    /* Other alternatives for checking are:
    || cache.hasOwnProperty(val) or !!cache[val]
    || but wouldn't work if the results of those
    || executions were falsy values.
    */
  }

  // We create and name the actual function to be used
  function factorial(num) {
    return (num === 0)? 1 : num * factorial(num - 1);
  } // End of factorial function

  /* We return the function that checks, not the one
  || that computes because  it happens to be recursive,
  || if it weren't you could avoid creating an extra
  || function in this self-invoking closure function.
  */
  return checkCache; 
}());

Maintenant, nous pouvons commencer à l'utiliser:

Voilà comment c'est fait

Maintenant que je commence à réfléchir à ce que je faisais, si je devais augmenter de 1 au lieu de décroissent de num, je pourrais avoir mis en cache tous les factorielles de 1 à num dans le cache récursive, mais je partirai pour vous.

C'est génial mais que faire si nous avons plusieurs paramètres ? C'est un problème? Pas tout à fait, nous pouvons faire quelques astuces comme l'utilisation de JSON.stringify () sur le tableau d'arguments ou même une liste de valeurs dont dépendra la fonction (pour les approches orientées objet). Ceci est fait pour générer une clé unique avec tous les arguments et dépendances inclus.

Nous pouvons également créer une fonction qui "mémorise" d'autres fonctions, en utilisant le même concept de portée que précédemment (en renvoyant une nouvelle fonction qui utilise l'original et a accès à l'objet de cache):

AVERTISSEMENT: la syntaxe ES6, si vous ne l'aimez pas, remplace ... par rien et utilise le var args = Array.prototype.slice.call(null, arguments); tour; remplacez const et let avec var, et les autres choses que vous connaissez déjà.

function memoize(func) {
  let cache = {};

  // You can opt for not naming the function
  function memoized(...args) {
    const argsKey = JSON.stringify(args);
    
    // The same alternatives apply for this example
    if (argsKey in cache) {
      console.log(argsKey + ' was/were in cache :D');
      return cache[argsKey];
    } else {
      cache[argsKey] = func.apply(null, args); // Cache it
      return cache[argsKey]; // And then return it
    }
  }

  return memoized; // Return the memoized function
}

Notez maintenant que cela fonctionnera pour plusieurs arguments mais ne sera pas très utile dans les méthodes orientées objet, je pense, vous aurez besoin d'un objet supplémentaire pour les dépendances. En outre, func.apply(null, args) peut être remplacé par func(...args) car la déstructuration des tableaux les enverra séparément plutôt que sous forme de tableau. Aussi, juste pour référence, le passage d'un tableau en tant qu'argument à func ne fonctionnera que si vous utilisez Function.prototype.apply comme je l'ai fait.

Pour utiliser la méthode ci-dessus, vous n'avez qu'à:

const newFunction = memoize(oldFunction);

// Assuming new oldFunction just sums/concatenates:
newFunction('meaning of life', 42);
// -> "meaning of life42"

newFunction('meaning of life', 42); // again
// => ["meaning of life",42] was/were in cache :D
// -> "meaning of life42"