Qu'Est-Ce Que L'Optimisation Des Appels De Queue?

très simplement, qu'est-ce que l'optimisation des appels de queue? Plus précisément, est-ce que quelqu'un peut montrer quelques petits extraits de code où ils pourraient être appliqués, et où ils ne le sont pas, avec une explication de pourquoi?

607
demandé sur ks1322 2008-11-22 09:56:32
la source

8 ответов

l'optimisation de L'appel de queue est où vous êtes en mesure d'éviter d'allouer un nouveau cadre de pile pour une fonction parce que la fonction d'appel retournera simplement la valeur qu'elle obtient de la fonction appelée. L'utilisation la plus courante est tail-recursion, où une fonction récursive écrite pour tirer profit de l'optimisation de tail-call peut utiliser l'espace de pile constant.

Scheme est l'un des rares langages de programmation qui garantissent dans les spécifications que toute mise en œuvre doit fournir cette optimisation (JavaScript fait aussi, à partir de ES6) , voici donc 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 de queue parce que lorsque l'appel récursif est fait, la fonction doit garder une trace de la multiplication qu'elle doit faire avec le résultat après le retour de l'appel. En tant que tel, la pile ressemble à ce qui suit:

(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 le queue recursive factorielle regarde 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 trace de la même quantité de données pour chaque appel à fact-tail parce que nous retournons simplement la valeur que nous obtenons directement 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-queue-récursive, et en tant que telles grandes valeurs peuvent causer un débordement de la pile.

571
répondu Kyle Cronin 2018-08-01 23:31:20
la source

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

Nous commençons par l'évidence définition récursive

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

une fonction se termine par un appel de queue 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.

même si fac() semble queue-récursive à première vue, il n'est pas comme ce que qui se passe en réalité est

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

ie la dernière opération est la multiplication et non l'appel de fonction.

cependant, il est possible de réécrire fac() pour être tail-recursive en passant la valeur accumulée en bas de la chaîne d'appel comme argument supplémentaire et en ne passant que le résultat final en haut à nouveau que la 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? Parce que nous revenons immédiatement après l'appel de queue, nous peut se débarrasser du cadre empilé précédent avant d'invoquer la fonction en position queue, ou, en cas de fonctions récursives, réutiliser le cadre empilé 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;
}

ce qui peut être inliné 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;
}

qui est l'équivalent de

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 itération, ce qui est beaucoup plus efficace que vous évitez fonction Appel overhead et utilisez seulement une quantité constante d'espace de pile.

452
répondu Christoph 2015-07-08 16:57:50
la source

TCO (Tail Call Optimization) est le processus par lequel un compilateur intelligent peut faire un appel à une fonction et ne pas prendre d'espace de pile supplémentaire. La seule 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 (Note: g peut être f ). La clé ici est que f n'a plus besoin d'espace de pile - il appelle simplement g et ensuite retourne ce que g retournerait. Dans ce cas, l'optimisation peut être faite que g tourne juste et renvoie n'importe quelle valeur qu'il aurait à la chose qui a appelé F.

cette optimisation peut faire que les appels récursifs prennent de l'espace de pile constant, plutôt que d'exploser.

exemple: cette fonction factorielle n'est pas extensible:

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

cette fonction fait des choses en plus d'appeler une autre fonction dans sa déclaration de retour.

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.

151
répondu Claudiu 2018-05-23 17:18:57
la source

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 l'article de blog

"Ce que le diable est: Un appel tail"

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

considérez, pour un instant, cette simple fonction:

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

Alors, que pouvez-vous, ou plutôt votre compilateur de langage, ne? Eh bien, ce qu'il peut faire est de transformer le code de la forme return somefunc(); dans la séquence de bas niveau pop stack frame; goto somefunc(); . Dans notre exemple, cela signifie avant que nous appelions bar , foo se nettoie et puis, plutôt que d'appeler bar comme un sous-programme, nous faisons une opération de bas niveau goto au début de bar . Foo 's déjà nettoyé lui-même hors de la pile, donc 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é foo , plutôt que de la renvoyer à foo qui la retournerait ensuite à son interlocuteur.

et sur la recursion de la queue:

Retursion de queue se produit si une fonction, comme sa dernière opération, retourne le résultat de s'appeler . La recursion de la queue est plus facile à traiter car plutôt que de ayant pour sauter au début d'un hasard fonctionner quelque part, vous faites juste un goto de retour au début de vous - même, ce qui est une chose très simple à faire.

pour 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 est à quel point il est succinct et facile à saisir pour ceux qui viennent d'un langage impératif d'arrière-plan (C, C++, Java)

46
répondu btiernay 2016-02-12 23:57:28
la source

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

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

vous voyez, normalement pendant la récursion, le runtime doit garder une trace de tous les appels récursifs, de sorte que lorsqu'un retourne il peut le reprendre à l'appel précédent et ainsi de suite. (Essayez manuellement l'écriture du résultat d'un appel récursif pour avoir une idée visuelle de la façon dont cela fonctionne.) Le suivi de tous les appels prend de la place, ce qui devient significatif lorsque la fonction s'appelle elle-même beaucoup. Mais avec TCO, il peut simplement dire "revenir au début, seulement cette fois changer les valeurs des paramètres à ces nouveaux."Il peut le faire parce que rien après l'appel récursif se réfère à ces valeurs.

12
répondu J Cooper 2008-11-22 10:09:41
la source

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 s'exécuter rapidement hors de l'espace de pile. L'optimisation des appels de queue est un moyen par lequel vous pouvez créer un algorithme de style récursif qui utilise l'espace de pile constant, donc il ne se développe pas et vous obtenez des erreurs de pile.

6
répondu BobbyShaftoe 2008-11-22 10:05:02
la source
  1. nous devrions nous assurer qu'il n'y a pas d'instructions goto dans la fonction elle-même .. pris en charge par fonction appel étant la dernière chose dans la fonction callee.

  2. les récursions à grande échelle peuvent l'utiliser pour des optimisations, mais à petite échelle, l'instruction "overhead" pour faire l'appel de fonction "tail call" réduit le but réel.

  3. TCO pourrait causer un de la fonction:

    void eternity()
    {
        eternity();
    }
    
4
répondu grillSandwich 2012-08-20 15:30:25
la source

fonction Récursive approche a un problème. Il construit une pile d'appels de taille O(n), ce qui rend notre coût total de mémoire O(N). Cela le rend vulnérable à une erreur de débordement de pile, où la pile d'appels devient trop grande et manque d'espace. Système d'optimisation des coûts de queue (TCO). Où il peut optimiser les fonctions récursives pour éviter de constituer une pile d'appels de grande taille et donc économiser le coût de mémoire.

il y a beaucoup de langues qui font TCO comme (Javascript, Ruby et quelques C) où comme Python et Java ne font pas TCO.

le langage JavaScript a confirmé en utilisant:) http://2ality.com/2015/06/tail-call-optimization.html

1
répondu Rupesh Kumar Tiwari 2018-07-30 04:34:59
la source