Pregunta ¿Qué es la optimización de llamadas de cola?


Muy simple, ¿qué es la optimización de la cola de llamada? Más específicamente, ¿alguien puede mostrar algunos pequeños fragmentos de código donde podría aplicarse, y dónde no, con una explicación de por qué?


593
2017-11-22 06:56


origen


Respuestas:


La optimización de llamada de cola es donde puede evitar asignar un nuevo marco de pila para una función porque la función de llamada simplemente devolverá el valor que obtiene de la función llamada. El uso más común es recursividad de cola, donde una función recursiva escrita para aprovechar la optimización de la cola de llamada puede usar el espacio de pila constante.

Scheme es uno de los pocos lenguajes de programación que garantiza en las especificaciones que cualquier implementación debe proporcionar esta optimización (JavaScript también, comenzando con ES6), aquí hay dos ejemplos de la función factorial en 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 primera función no es recursiva de cola porque cuando se realiza la llamada recursiva, la función necesita realizar un seguimiento de la multiplicación que necesita hacer con el resultado después de que la llamada retorna. Como tal, la pila se ve de la siguiente manera:

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

Por el contrario, el seguimiento de pila para el factorial recursivo de cola se ve de la siguiente manera:

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

Como puede ver, solo necesitamos hacer un seguimiento de la misma cantidad de datos para cada llamada a fact-tail porque simplemente estamos devolviendo el valor que obtenemos directamente a la parte superior. Esto significa que incluso si tuviera que llamar (hecho 1000000), necesito solo la misma cantidad de espacio que (hecho 3). Este no es el caso con el hecho no recursivo de cola, y como tales valores grandes pueden causar un desbordamiento de pila.


562
2017-11-22 07:07



Veamos un ejemplo simple: la función factorial implementada en C.

Comenzamos con la definición recursiva obvia

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

Una función finaliza con una llamada final si la última operación antes de que la función regrese es otra llamada a función. Si esta invocación invoca la misma función, es recursiva de cola.

Aunque fac() parece recursivo a primera vista, no es como lo que realmente sucede es

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

es decir, la última operación es la multiplicación y no la llamada a la función.

Sin embargo, es posible reescribir fac() ser recursivo de cola al pasar el valor acumulado por la cadena de llamadas como un argumento adicional y pasar nuevamente el resultado final como el valor de retorno:

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);
}

Ahora, ¿por qué es esto útil? Debido a que regresamos inmediatamente después de la llamada final, podemos descartar el fotograma de pila anterior antes de invocar la función en la posición de cola, o, en el caso de funciones recursivas, reutilizar el fotograma de la pila tal como está.

La optimización de la llamada final transforma nuestro código recursivo en

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

Esto puede ser insertado en fac() y llegamos a

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

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

que es equivalente a

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

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

    return acc;
}

Como podemos ver aquí, un optimizador suficientemente avanzado puede reemplazar la recursividad de cola con iteración, que es mucho más eficiente ya que evita la sobrecarga de llamada de función y solo utiliza una cantidad constante de espacio de pila.


437
2018-03-22 00:04



TCO (Tail Call Optimization) es el proceso mediante el cual un compilador inteligente puede realizar una llamada a una función y no tomar espacio de pila adicional. los única situación en la que esto sucede es si la última instrucción ejecutada en una función F es una llamada a una función g (Nota: gramo puede ser F) La clave aquí es que F ya no necesita espacio de pila, simplemente llama gramo y luego devuelve lo que sea gramo volvería. En este caso, se puede hacer la optimización de que g simplemente se ejecute y devuelva el valor que tendría para lo que se llamó f.

Esta optimización puede hacer que las llamadas recursivas tomen un espacio de pila constante, en lugar de explotar.

Ejemplo: esta función factorial no es TCOptimizable:

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

Esta función hace cosas además de llamar a otra función en su declaración de devolución.

Esta función a continuación es 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)

Esto se debe a que lo último que ocurre en cualquiera de estas funciones es llamar a otra función.


149
2017-11-22 07:12



Probablemente la mejor descripción de alto nivel que he encontrado para las llamadas finales, las llamadas de cola recursivas y la optimización de la cola de cola es la publicación del blog

"¿Qué diablos es: una llamada de cola" 

por Dan Sugalski. En la optimización de la cola de llamada, escribe:

Considera, por un momento, esta simple función:

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

Entonces, ¿qué puede usted, o más bien su compilador de lenguaje, hacer? Bueno, lo que puede hacer es cambiar el código de la forma return somefunc(); en la secuencia de bajo nivel pop stack frame; goto somefunc();. En nuestro ejemplo, eso significa que antes de llamar bar, foo se limpia y luego, en lugar de llamar bar como una subrutina, hacemos un bajo nivel goto operación al comienzo de bar. FooYa se ha limpiado de la pila, así que cuando bar comienza, se ve como quien llamó foo realmente ha llamado bar, y cuando bar devuelve su valor, lo devuelve directamente a quien llamó foo, en lugar de devolverlo a foo que luego lo devolvería a su llamador.

Y en la recursividad de la cola:

La recursión de cola ocurre si una función, como su última operación, devoluciones   el resultado de llamarse a sí mismo. La recursividad de la cola es más fácil de tratar   porque en lugar de tener que saltar al comienzo de algunos al azar   funcionar en alguna parte, simplemente haz un regreso al comienzo de   usted mismo, que es algo muy simple de hacer.

Para que esto:

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

se convierte silenciosamente en:

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

Lo que me gusta de esta descripción es lo sucinto y fácil de entender para quienes provienen de un contexto de lenguaje imperativo (C, C ++, Java)


44
2017-08-26 01:27



Tenga en cuenta en primer lugar que no todos los idiomas lo admiten.

TCO se aplica a un caso especial de recursión. La esencia de esto es que si lo último que haces en una función es llamarse a sí mismo (por ejemplo, se llama a sí mismo desde la posición de "cola"), el compilador puede optimizarlo para actuar como iteración en lugar de recursión estándar.

Verá, normalmente durante la recursión, el tiempo de ejecución necesita realizar un seguimiento de todas las llamadas recursivas, de modo que cuando se devuelve puede reanudarse en la llamada anterior y así sucesivamente. (Intente escribir manualmente el resultado de una llamada recursiva para tener una idea visual de cómo funciona esto). Hacer un seguimiento de todas las llamadas ocupa espacio, lo que se vuelve significativo cuando la función se autodenomina mucho. Pero con TCO, solo puede decir "volver al principio, solo que esta vez cambie los valores de los parámetros a estos nuevos". Puede hacerlo porque nada después de la llamada recursiva se refiere a esos valores.


10
2017-11-22 07:09



Mira aquí:

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

Como probablemente sepa, las llamadas a funciones recursivas pueden causar estragos en una pila; es fácil quedarse rápidamente sin espacio en la pila. La optimización de llamada de cola es la forma mediante la cual puede crear un algoritmo de estilo recursivo que utiliza el espacio de pila constante, por lo tanto, no crece y crece y obtiene errores de pila.


5
2017-11-22 07:05



  1. Deberíamos asegurarnos de que no haya declaraciones goto en la función en sí ... atendidas por la función de llamada que es lo último en la función llamada.

  2. Las recurrencias a gran escala pueden usar esto para optimizaciones, pero a pequeña escala, la sobrecarga de instrucciones para hacer que la función llame a una llamada final reduce el propósito real.

  3. TCO podría causar una función de ejecución permanente:

    void eternity()
    {
        eternity();
    }
    

4
2017-08-20 10:12