Question Qu'est-ce que l'optimisation de l'appel de queue?


Très simplement, qu'est-ce que l'optimisation des appels? Plus précisément, Quelqu'un peut-il montrer quelques petits extraits de code où il pourrait être appliqué, et où non, avec une explication de pourquoi?


593
2017-11-22 06:56


origine


Réponses:


L'optimisation des appels de queue est l'endroit où vous pouvez éviter d'allouer un nouveau cadre de pile pour une fonction car la fonction appelante retournera simplement la valeur qu'elle obtient de la fonction appelée. L'utilisation la plus fréquente est la récursion de queue, où une fonction récursive écrite pour tirer parti de l'optimisation de l'appel de queue peut utiliser un espace de pile constant.

Scheme est l'un des rares langages de programmation qui garantissent dans les spécifications que toute implémentation doit fournir cette optimisation (JavaScript aussi, en commençant par ES6), donc voici deux exemples de la fonction factorielle dans Scheme:

(define (fact x)
  (if (= x 0) 1
      (* x (fact (- x 1)))))

(define (fact x)
  (define (fact-tail x accum)
    (if (= x 0) accum
        (fact-tail (- x 1) (* x accum))))
  (fact-tail x 1))

La première fonction n'est pas récursive en queue car lorsque l'appel récursif est fait, la fonction doit garder trace de la multiplication dont elle a besoin pour le résultat après le retour de l'appel. En tant que tel, la pile ressemble à ceci:

(fact 3)
(* 3 (fact 2))
(* 3 (* 2 (fact 1)))
(* 3 (* 2 (* 1 (fact 0))))
(* 3 (* 2 (* 1 1)))
(* 3 (* 2 1))
(* 3 2)
6

En revanche, la trace de la pile pour la factorielle récursive de la queue se présente comme suit:

(fact 3)
(fact-tail 3 1)
(fact-tail 2 3)
(fact-tail 1 6)
(fact-tail 0 6)
6

Comme vous pouvez le voir, nous avons seulement besoin de garder la même quantité de données pour chaque appel à fact-tail car nous retournons simplement la valeur que nous obtenons jusqu'au sommet. Cela signifie que même si je devais appeler (fait 1000000), je n'ai besoin que de la même quantité d'espace que (fait 3). Ce n'est pas le cas avec le fait non-récursif de queue, et en tant que telles de grandes valeurs peuvent provoquer un débordement de pile.


562
2017-11-22 07:07



Parcourons un exemple simple: la fonction factorielle implémentée en C.

Nous commençons avec la définition récursive évidente

unsigned fac(unsigned n)
{
    if (n < 2) return 1;
    return n * fac(n - 1);
}

Une fonction se termine par un appel de fin si la dernière opération avant le retour de la fonction est un autre appel de fonction. Si cet appel invoque la même fonction, il est récursif à la queue.

Même si fac() ressemble à la queue récursive à première vue, ce n'est pas comme ce qui se passe réellement

unsigned fac(unsigned n)
{
    if (n < 2) return 1;
    unsigned acc = fac(n - 1);
    return n * acc;
}

c'est-à-dire que la dernière opération est la multiplication et non l'appel de la fonction.

Cependant, il est possible de réécrire fac() être récursif en queue en passant la valeur accumulée dans la chaîne d'appel comme argument supplémentaire et en ne faisant passer que le résultat final comme valeur de retour:

unsigned fac(unsigned n)
{
    return fac_tailrec(1, n);
}

unsigned fac_tailrec(unsigned acc, unsigned n)
{
    if (n < 2) return acc;
    return fac_tailrec(n * acc, n - 1);
}

Maintenant, pourquoi est-ce utile? Puisque nous revenons immédiatement après l'appel de queue, nous pouvons rejeter l'empilement précédent avant d'invoquer la fonction en position de queue, ou, dans le cas de fonctions récursives, réutiliser l'empilement tel quel.

L'optimisation de l'appel de queue transforme notre code récursif en

unsigned fac_tailrec(unsigned acc, unsigned n)
{
TOP:
    if (n < 2) return acc;
    acc = n * acc;
    n = n - 1;
    goto TOP;
}

Cela peut être incorporé dans fac() et nous arrivons à

unsigned fac(unsigned n)
{
    unsigned acc = 1;

TOP:
    if (n < 2) return acc;
    acc = n * acc;
    n = n - 1;
    goto TOP;
}

ce qui est équivalent à

unsigned fac(unsigned n)
{
    unsigned acc = 1;

    for (; n > 1; --n)
        acc *= n;

    return acc;
}

Comme nous pouvons le voir ici, un optimiseur suffisamment avancé peut remplacer la récursion de queue par une itération, ce qui est beaucoup plus efficace car vous évitez le surdébit d'appel de fonction et n'utilisez qu'une quantité constante d'espace de pile.


437
2018-03-22 00:04



TCO (Tail Call Optimization) est le processus par lequel un compilateur intelligent peut faire un appel à une fonction et ne prendre aucun espace de pile supplémentaire. le seule la situation dans laquelle cela se produit est si la dernière instruction exécutée dans une fonction F est un appel à une fonction g (Remarque: g peut être F). La clé ici est que F n'a plus besoin d'espace de pile - il appelle simplement g puis renvoie tout g retournerais. Dans ce cas, l'optimisation peut être faite que g court et renvoie la valeur qu'il aurait à la chose appelée f.

Cette optimisation permet aux appels récursifs de prendre un espace de pile constant plutôt que d'exploser.

Exemple: cette fonction factorielle n'est pas TCOptimizable:

def fact(n):
    if n == 0:
        return 1
    return n * fact(n-1)

Cette fonction fait les choses en plus d'appeler une autre fonction dans son instruction return.

Cette fonction ci-dessous est TCOptimizable:

def fact_h(n, acc):
    if n == 0:
        return acc
    return fact_h(n-1, acc*n)

def fact(n):
    return fact_h(n, 1)

C'est parce que la dernière chose à se produire dans l'une de ces fonctions est d'appeler une autre fonction.


149
2017-11-22 07:12



Probablement la meilleure description de haut niveau que j'ai trouvé pour les appels de queue, les appels de queue récursifs et l'optimisation des appels de queue est le blog

"Que diable est: un appel de queue" 

par Dan Sugalski. Sur l'optimisation des appels de queue, il écrit:

Considérons, pour un moment, cette fonction simple:

sub foo (int a) {
  a += 15;
  return bar(a);
}

Alors, que pouvez-vous, ou plutôt votre compilateur de langue, faire? Eh bien, ce qu'il peut faire est de tourner le code du formulaire return somefunc(); dans la séquence de bas niveau pop stack frame; goto somefunc();. Dans notre exemple, cela signifie avant d'appeler bar, foo se nettoie et ensuite, plutôt que d'appeler bar comme un sous-programme, nous faisons un bas niveau goto opération au début de bar. Fooest déjà nettoyé de la pile, alors quand bar commence il ressemble à celui qui a appelé foo a vraiment appelé bar, et quand bar renvoie sa valeur, il la renvoie directement à celui qui a appelé fooplutôt que de le renvoyer à foo qui le renvoie ensuite à son appelant.

Et sur la récursivité de la queue:

La récursion de queue se produit si une fonction, comme sa dernière opération, résultats   le résultat de s'appeler. La récurrence de la queue est plus facile à gérer   parce que plutôt que d'avoir à sauter au début de certains aléatoires   fonction quelque part, vous venez de faire un retour au début de   vous-même, ce qui est une chose simple à faire.

Alors que ceci:

sub foo (int a, int b) {
  if (b == 1) {
    return a;
  } else {
    return foo(a*a + a, b - 1);
  }

se transforme tranquillement en:

sub foo (int a, int b) {
  label:
    if (b == 1) {
      return a;
    } else {
      a = a*a + a;
      b = b - 1;
      goto label;
   }

Ce que j'aime dans cette description, c'est à quel point elle est succincte et facile à saisir pour ceux qui viennent d'un contexte de langage impératif (C, C ++, Java)


44
2017-08-26 01:27



Notez tout d'abord que toutes les langues ne le supportent pas.

TCO s'applique à un cas particulier de récursion. L'essentiel est que si la dernière chose que vous faites dans une fonction est d'appeler elle-même (par exemple, elle s'appelle de la position "queue"), cela peut être optimisé par le compilateur pour agir comme itération au lieu de la récursivité standard.

Vous voyez, normalement pendant la récursion, le runtime doit garder la trace de tous les appels récursifs, de sorte que quand on revient, il peut reprendre à l'appel précédent et ainsi de suite. (Essayez d'écrire manuellement le résultat d'un appel récursif pour avoir une idée visuelle de la façon dont cela fonctionne.) Garder une trace de tous les appels prend de l'espace, ce qui devient important lorsque la fonction s'appelle beaucoup. Mais avec TCO, il peut juste dire "revenir au début, seulement cette fois changer les valeurs des paramètres à ces nouveaux." Il peut le faire car rien après l'appel récursif ne fait référence à ces valeurs.


10
2017-11-22 07:09



Regardez ici:

http://tratt.net/laurie/tech_articles/articles/tail_call_optimization

Comme vous le savez probablement, les appels de fonction récursifs peuvent faire des ravages sur une pile; il est facile de manquer rapidement d'espace de pile. L'optimisation des appels de queue permet de créer un algorithme de style récursif qui utilise un espace de pile constant. Par conséquent, il ne grandit pas et ne se développe pas et vous obtenez des erreurs de pile.


5
2017-11-22 07:05



  1. Nous devons nous assurer qu'il n'y a pas d'instructions goto dans la fonction elle-même. Pris soin par l'appel de fonction étant la dernière chose dans la fonction de l'appelé.

  2. Les récursions à grande échelle peuvent l'utiliser pour des optimisations, mais à petite échelle, le surcoût d'instruction pour que la fonction appelle un appel de fin réduit l'objectif réel.

  3. Le coût total de possession peut entraîner une fonction permanente:

    void eternity()
    {
        eternity();
    }
    

4
2017-08-20 10:12