Mémoire de fonction des notes d'apprentissage JavaScript

Cet article présente principalement la mémoire de fonction des notes d'étude JavaScript L'éditeur pense que c'est assez bon. Je vais maintenant partager le code source JavaScript avec vous et le donner comme référence. Si vous êtes intéressé par JavaScript, veuillez suivre l'éditeur pour y jeter un œil

Cet article explique l'implémentation de la mémoire de fonctions et de la séquence de Fibonacci et le partage avec tout le monde, les détails sont les suivants

Définition

La mémoire de fonction fait référence à la mise en cache du dernier résultat du calcul Lors du prochain appel, si les mêmes paramètres sont rencontrés, les données dans le cache seront renvoyées. directement.

Par exemple :

function add(a, b) {
  return a + b;
}

// 假设 memorize 可以实现函数记忆
var memoizedAdd = memorize(add);

memoizedAdd(1, 2) // 3
memoizedAdd(1, 2) // 相同的参数，第二次调用时，从缓存中取出数据，而非重新计算一次

Principe

Il est très simple de mettre en œuvre une telle fonction de mémorisation. En principe, vous seul. besoin de combiner les paramètres avec Les données de résultat correspondantes sont stockées dans un objet. Lors de l'appel, il est jugé si les données correspondant au paramètre existent. Si elles existent, les données de résultat correspondantes sont renvoyées.

Première version

Écrivons une version :

// 第一版 (来自《JavaScript权威指南》)
function memoize(f) {
  var cache = {};
  return function(){
    var key = arguments.length + Array.prototype.join.call(arguments, ",");
    if (key in cache) {
      return cache[key]
    }
    else return cache[key] = f.apply(this, arguments)
  }
}

Testons-la :

var add = function(a, b, c) {
 return a + b + c
}

var memoizedAdd = memorize(add)

console.time('use memorize')
for(var i = 0; i < 100000; i++) {
  memoizedAdd(1, 2, 3)
}
console.timeEnd(&#39;use memorize&#39;)

console.time(&#39;not use memorize&#39;)
for(var i = 0; i < 100000; i++) {
  add(1, 2, 3)
}
console.timeEnd(&#39;not use memorize&#39;)

Dans Chrome, l'utilisation de la mémorisation prend environ 60 ms. Si nous n'utilisez pas la fonction pour mémoriser, cela prend environ 1,3 ms.

Remarque

Quoi, nous avons utilisé la fonction mémoire apparemment avancée, mais cela s'est avéré prendre plus de temps, près de 60 fois dans cet exemple !

Ainsi, la mémoire de fonctions n'est pas omnipotente. Si vous regardez ce scénario simple, elle n'est en fait pas adaptée à la mémoire de fonctions.

Il convient de noter que la mémoire de fonctions n'est qu'une programmation. Elle sacrifie essentiellement la complexité spatiale de l'algorithme en échange d'une meilleure complexité temporelle. Le code dans le client JavaScript est souvent complexe en termes de temps d'exécution. devient un goulot d'étranglement, donc dans la plupart des scénarios, cette approche consistant à sacrifier l'espace au profit du temps pour améliorer l'efficacité de l'exécution du programme est très souhaitable.

Deuxième version

Comme la première version utilise la méthode join, on peut facilement penser que lorsque le paramètre est un objet, la méthode toString sera automatiquement appelé Convertissez-le en [Object object], puis concaténez chaîne comme valeur clé. Écrivons une démo pour vérifier ce problème :

var propValue = function(obj){
  return obj.value
}

var memoizedAdd = memorize(propValue)

console.log(memoizedAdd({value: 1})) // 1
console.log(memoizedAdd({value: 2})) // 1

Les deux renvoient 1, ce qui est évidemment un problème, voyons donc comment la fonction de mémorisation du trait de soulignement est implémentée :

// 第二版 (来自 underscore 的实现)
var memorize = function(func, hasher) {
  var memoize = function(key) {
    var cache = memoize.cache;
    var address = '' + (hasher ? hasher.apply(this, arguments) : key);
    if (!cache[address]) {
      cache[address] = func.apply(this, arguments);
    }
    return cache[address];
  };
  memoize.cache = {};
  return memoize;
};

Comme le montre cette implémentation, le trait de soulignement utilise le premier paramètre de la fonction comme clé par défaut, donc si vous utilisez

var add = function(a, b, c) {
 return a + b + c
}

var memoizedAdd = memorize(add)

memoizedAdd(1, 2, 3) // 6
memoizedAdd(1, 2, 4) // 6

directement, il y aura certainement un problème si vous souhaitez en prendre en charge plusieurs. paramètres, nous avons besoin de transmettre la fonction de hachage et de personnaliser la valeur de la clé stockée. Nous envisageons donc d'utiliser JSON.stringify :

var memoizedAdd = memorize(add, function(){
  var args = Array.prototype.slice.call(arguments)
  return JSON.stringify(args)
})

console.log(memoizedAdd(1, 2, 3)) // 6
console.log(memoizedAdd(1, 2, 4)) // 7

Si vous utilisez JSON.stringify, le problème selon lequel le paramètre est un objet peut également être résolu, car ce qui est stocké est la chaîne après sérialisation de l'objet .

Scénarios applicables

Nous prenons la séquence de Fibonacci comme exemple :

var count = 0;
var fibonacci = function(n){
  count++;
  return n < 2? n : fibonacci(n-1) + fibonacci(n-2);
};
for (var i = 0; i <= 10; i++){
  fibonacci(i)
}

console.log(count) // 453

Nous constaterons que le décompte final est 453 , ce qui signifie que la fonction de Fibonacci a été appelée 453 fois ! Peut-être que vous pensez, je viens de boucler sur 10, pourquoi a-t-il été appelé tant de fois, alors analysons-le en détail :

Lorsque fib(0) est exécuté, il est appelé 1 fois

Lors de l'exécution de fib(1), il est appelé une fois

Lors de l'exécution de fib(2), cela équivaut à fib(1) + fib(0) plus fib(2) lui-même cette fois, un total de 1 + 1 + 1 = 3 fois

Lors de l'exécution de fib(3), cela équivaut à fib(2) + fib(1) plus fib(3) lui-même cette fois, un total de 3 + 1 + 1 = 5 fois

Lors de l'exécution de fib(4), cela équivaut à fib(3) + fib(2) plus fib(4) lui-même cette fois, un total de 5 + 3 + 1 = 9 fois

Quand Lors de l'exécution de fib(5), cela équivaut à fib(4) + fib(3) plus fib(5) lui-même cette fois, un total de 9 + 5 + 1 = 15 fois

lors de l'exécution de fib(6) , équivalent à fib(5) + fib(4) plus fib(6) lui-même cette fois, un total de 15 + 9 + 1 = 25 fois

Lors de l'exécution de fib (7), cela équivaut à fib(6 ) + fib(5) plus fib(7) lui-même cette fois, un total de 25 + 15 + 1 = 41 fois

Lors de l'exécution de fib(8), c'est équivalent à fib(7) + fib(6) En ajoutant fib(8) lui-même cette fois, un total de 41 + 25 + 1 = 67 fois

Lors de l'exécution de fib(9), cela équivaut à fib(8) + fib(7) plus fib(9) Cette fois-ci, un total de 67 + 41 + 1 = 109 fois

Lorsque fib(10) est exécuté, cela équivaut à fib(9 ) + fib(8) plus fib(10) lui-même cette fois, un total de 109 + 67 + 1 = 177 fois
Donc le nombre total d'exécutions est : 177 + 109 + 67 + 41 + 25 + 15 + 9 + 5 + 3 + 1 + 1 = 453 fois !

Et si on utilisait la mémoire de fonctions ?

var count = 0;
var fibonacci = function(n) {
  count++;
  return n < 2 ? n : fibonacci(n - 1) + fibonacci(n - 2);
};

fibonacci = memorize(fibonacci)

for (var i = 0; i <= 10; i++) {
  fibonacci(i)
}

console.log(count) // 12

Nous constaterons que le nombre total final de fois est de 12 fois. Grâce à l'utilisation de la mémoire de fonction, le nombre d'appels est réduit de 453 fois à 12 fois !

N'oubliez pas pendant que vous êtes excité. Réfléchissez : Pourquoi c'est 12 fois ?

Les résultats de 0 à 10 sont stockés une fois chacun. Cela devrait être 11 fois ? Hé, d'où vient ce temps supplémentaire ?

Nous devons donc également examiner attentivement notre méthode d'écriture. Dans notre méthode d'écriture, nous écrasons en fait la fonction fibonacci d'origine par la fonction fibonacci générée. Lorsque nous exécutons fibonacci(0), la fonction est exécutée une fois et le cache. est { 0 : 0}, mais lorsque nous exécutons fibonacci(2), nous exécutons fibonacci(1) + fibonacci(0), car la valeur de fibonacci(0) est 0, le résultat de !cache[address] est vrai, et fibonacci sera exécuté à nouveau la fonction. Il s'avère que le temps supplémentaire est là !

Peut-être avez-vous l'impression que Fibonacci n'est pas utilisé dans le développement quotidien, et cet exemple semble avoir peu de valeur pratique. En fait, cet exemple est utilisé pour illustrer un scénario d'utilisation, c'est-à-dire si un grand nombre de. des répétitions sont nécessaires Pour les calculs, ou lorsqu'un grand nombre de calculs dépendent des résultats précédents, vous pouvez envisager d'utiliser la mémoire de fonctions. Et lorsque vous rencontrerez ce genre de scène, vous le saurez.

Recommandations associées :

Analyse de l'utilisation de la liaison de la fonction JavaScript

Explication détaillée de la limitation et du rebond anti-tremblement de la fonction JavaScript

Un exemple d'utilisation de la liaison de fonction JavaScript

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!