Question sur « Queue Appel Optimisation » Article

StackOverflow https://stackoverflow.com/questions/4707888

Question

J'ai une question concernant cet article .

Entre ce code 

function odds(n, p) {
  if(n == 0) {
    return 1
  } else {
    return (n / p) * odds(n - 1, p - 1)
  }
}

et ce code 

(function(){
  var odds1 = function(n, p, acc) {
    if(n == 0) {
      return acc
    } else {
      return odds1(n - 1, p - 1, (n / p) * acc)
    }
  }

  odds = function(n, p) {
    return odds1(n, p, 1)
  }  
})()

1) Je suis confus au sujet de combien cela aide. Le deuxième extrait ont simplement un appel de queue qui crée moins de frais généraux, car il calcule ce dont il a besoin avant qu'il se dit à nouveau, ou est-il quelque chose de plus que je suis absent?

Si je comprends bien, l'appel de la queue est toujours pas éliminé, juste optimisé.

2) Et pourquoi il besoin d'être odds et odds1 de toute façon? On ne sait pas encore pour moi non plus.

Était-ce utile?

La solution

  

Je suis confus au sujet de combien cela aide. Le deuxième extrait ont simplement un appel de queue qui crée moins de frais généraux, car il calcule ce dont il a besoin avant qu'il se dit à nouveau, ou est-il quelque chose de plus que je suis absent?

     

Si je comprends bien, l'appel de la queue est toujours pas éliminé, juste optimisé.

Si la fin d'une procédure ressemble à ceci: 

push args
call foo
return

Ensuite, le compilateur peut optimiser les lignes juste 

jump startOfFoo

L'élimination de tout à fait l'appel de procédure.

  

Et pourquoi il faut être chances et odds1 de toute façon? On ne sait pas encore pour moi non plus.

Le « contrat » de odds prévoit seulement deux arguments - le troisième argument est juste un détail de mise en œuvre. Alors vous cacher loin dans une méthode interne, et de présenter un « emballage », comme l'API externe.

On pourrait appeler odds1 quelque chose comme oddsImpl et il rendrait plus clair, je pense.

Autres conseils

L'optimisation de la récursivité de queue est suit comme, dans le premier exemple, puisque vous ne pouvez pas calculer le résultat de la return (n / p) * odds(n - 1, p - 1) de multiplication jusqu'à ce que vous avez appelé chance (n-1), le interperator doit tenir notre position actuelle dans la mémoire (sur la pile), et ouvrir un nouvel appel à cote.

récursive, qui se produira dans le prochain appel aussi bien, et celle d'après et ainsi de suite. Nous avons donc n opérations en attente au moment où nous arrivons à la fin de notre récursivité et commencer à retourner le valeurset calcul des produits.

Dans le second exemple, étant donné que l'instruction de retour est exécuté return odds1(n - 1, p - 1, (n / p) * acc) simplement que nous pouvons calculer les arguments de la fonction, et simplement appeler le odds1 (n-1) sans tenir notre position actuelle . c'est là l'optimisation est, parce que maintenant je ne dois me rappeler où je suis à chaque fois que j'ouvre un nouveau cadre sur la pile.

Pensez-y comme références de livres. Imaginez que vous ouvrez un livre de cuisine et allez dans une certaine recette et les ingrédients sont répertoriés comme suit:

  1. sel
  2. les ingrédients sur la page suivante

la page suivante a

  1. poivre
  2. les ingrédients sur la page suivante

etc. comment voulez-vous dire ce que tous les ingrédients sont? vous devez vous rappeler ce que vous avez vu sur chaque page!

bien que le second exemple est plus comme la liste des ingrédients suivants:

  1. sel
  2. oublier, il suffit d'utiliser ce que vous voyez sur la page suivante

la page suivante a:

  1. sel
  2. poivre
  3. oublier, il suffit d'utiliser ce que vous voyez sur la page suivante

etc. au moment où vous atteignez la dernière page (notez que l'analogie est exacte en ce qu'aussi bien prendre la même quantité d'appels de fonction), vous avez tous les ingrédients, sans avoir à « garder en mémoire » ce que vous avez vu sur chaque page, parce qu'il est tout ce qu'il ya sur la dernière page!

Non affilié à StackOverflow
scroll top