Introduction aux fonctions JavaScript

Cet article présente principalement la fonction mémoire des notes d'apprentissage JavaScript. L'éditeur pense que c'est assez bon, je vais donc le partager avec vous maintenant et le donner comme référence. Venez jeter un œil avec l'éditeur

Cet article explique l'implémentation de la fonction mémoire 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 résultat du dernier 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 un tel une fonction de mémorisation Simple. En principe, il vous suffit de stocker les paramètres et les données de résultat correspondantes dans un objet, lors de l'appel, de déterminer si les données correspondant au paramètre existent, et de renvoyer les données de résultat correspondantes si elles existent.

Première édition

É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'utilisons pas la mémoire de fonction, 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 technique de programmation, qui sacrifie essentiellement la complexité spatiale de l'algorithme en échange d'une meilleure complexité temporelle. En JavaScript côté client, la complexité temporelle d'exécution du code devient souvent. goulet 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 [Objet objet], puis concaténez la chaîne en tant que 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, regardons donc comment la fonction memoize du 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

directement

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

var memoizedAdd = memorize(add)

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

Il doit y avoir un problème. Si nous voulons prendre en charge plusieurs paramètres, nous devons transmettre la fonction de hachage et 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 l'objet est stocké après la chaîne de sérialisation.

Scénarios applicables

Nous prenons comme exemple la séquence de Fibonacci :

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 de 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. La mémoire de fonction étant utilisée, le nombre d'appels est réduit de 453 fois. à 12 fois !

Pendant que vous êtes excité, n'oubliez pas de réfléchir : Pourquoi est-ce 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à !

Dites-m'en plus

Peut-être avez-vous l'impression que Fibonacci n'est pas utilisé dans le développement quotidien. Cet exemple donne l'impression qu'il n'a pas une grande valeur pratique. , cet exemple est utilisé pour illustrer un scénario d'utilisation, c'est-à-dire que si un grand nombre de calculs répétés sont nécessaires ou si 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.

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!