Pregunta sobre “Optimización de la llamada del extremo” Artículo

Question

Tengo una pregunta con respecto este artículo .

Entre el código

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

y el código

(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) Estoy confundido acerca de lo mucho que esto ayude. ¿El segundo fragmento simplemente tiene una llamada cola que genera menos gastos generales, ya que calcula lo que necesita antes de que se llama a sí mismo de nuevo, o hay algo más que me falta?

A mi entender, la llamada cola todavía no se elimina, simplemente optimizado.

2) ¿Y por qué es necesario que existan odds y odds1 de todos modos? Todavía no está claro para mí tampoco.

Answer 1

Estoy confundido acerca de lo mucho que esto ayude. ¿El segundo fragmento simplemente tiene una llamada cola que genera menos gastos generales, ya que calcula lo que necesita antes de que se llama a sí mismo de nuevo, o hay algo más que me falta?

A mi entender, la llamada cola todavía no se elimina, simplemente optimizado.

Si el final de un procedimiento se ve así:

push args
call foo
return

A continuación, el compilador puede optimizar esa distancia sólo

jump startOfFoo

La eliminación de la llamada al procedimiento completo.

Y ¿por qué es necesario que existan probabilidades y de todos modos odds1? Todavía no está claro para mí tampoco.

El "contrato" de odds especifica sólo dos argumentos - el tercer argumento es sólo un detalle de implementación. Así que se oculta de distancia, en un método interno, y presentar una "envoltura", como la API externa.

Se le podría llamar algo así como odds1 oddsImpl y sería hacerlo más claro, creo.

Answer 2

La primera versión no es cola recursiva porque después de obtener el valor de lo que tiene que odds(n - 1, p - 1) a continuación, se multiplica por (n / p), la segunda versión mueve esto en el cálculo de los parámetros de la función odds1 para que sea recursiva adecuadamente cola.

Si nos fijamos en la pila de llamadas a continuación, la primera sería algo así:

odds(2, 3)
  odds(1, 2)
    odds(0, 1)
    return 1
  return 1/2 * 1
return 2/3 * 1/2

mientras que el segundo sería:

odds(2, 3)
  odds1(2, 3, 1)
    odds1(1, 2, 2/3)
      odds1(0, 1, 1/2 * 2/3)
      return 1/3
    return 1/3
  return 1/3
return 1/3

porque estás simplemente devolviendo el valor de la llamada recursiva el compilador puede optimizar esta facilidad:

odds(2, 3)
#discard stackframe
odds1(2, 3, 1)
#discard stackframe
odds1(1, 2, 2/3)
#discard stackframe
odds1(0, 1, 1/3)
return 1/3

La razón de tener odds y odds1 es simplemente para suministrar el valor inicial del acumulador cuando otro código llama a esta función.

Answer 3

La optimización de recursión de cola es el siguiente, en el primer ejemplo ya no se puede calcular el resultado de la return (n / p) * odds(n - 1, p - 1) multiplicación hasta que haya llamado probabilidades (n-1), el interperator tiene que sostener nuestra posición actual en la memoria (en la pila), y abrir una nueva llamada a las probabilidades.

recursiva, que va a pasar en la siguiente llamada así, y la siguiente y así sucesivamente. Así que hemos operaciones n pendientes en el momento en que llegamos al final de nuestra recursividad y empezar a devolver el valuesand cálculo de los productos.

En el segundo ejemplo, ya que la instrucción de retorno es simplemente ejecutados return odds1(n - 1, p - 1, (n / p) * acc) podemos calcular los argumentos de la función, y simplemente llamar a la odds1 (n-1) sin mantener nuestra posición actual . aquí es donde la optimización es, porque ahora no tengo que recordar dónde estoy cada vez que abro un nuevo marco en la pila.

Piense en ello como referencias de libros. Imagínese que usted abre un libro de cocina y va a una receta determinada, y se enumeran los ingredientes de la siguiente manera:

1. sal
2. los ingredientes en la página siguiente

La siguiente página tiene

1. pimienta
2. los ingredientes en la página siguiente

etc. ¿cómo saber lo que todos los ingredientes son? usted tiene que recordar lo que viste en cada página!

aunque el segundo ejemplo es más como la lista de ingredientes siguiente:

1. sal
2. olvidar esto, sólo tiene que utilizar lo que se ve en la siguiente página

La siguiente página tiene:

1. sal
2. pimienta
3. olvidar esto, sólo tiene que utilizar lo que se ve en la siguiente página

etc. en el momento de llegar a la última página (nota que la analogía es exacta en la que ambos toman la misma cantidad de llamadas de función), que tiene todos los ingredientes, sin tener que "mantener en la memoria" lo que viste en cada página, porque es todo lo que hay en la última página!