Rendimiento del estilo recursivo vs acumulador

Question

Tenemos dos funciones que calculan el factorial de un número dado. El primero, !, usa un estilo de acumulador. El segundo, fact, usa recursión natural.

(define (! n0) 
    (local (;; accumulator is the product of all natural numbers in [n0, n) 
     (define (!-a n accumulator) 
     (cond 
      [(zero? n) accumulator] 
      [else (!-a (sub1 n) (* n accumulator))]))) 
    (!-a n0 1))) 

y

(define (fact n) 
    (cond 
    [(= 0 n) 1] 
    [else (* n (fact (- n 1)))])) 

En la parte inferior de la sección 31, HtDP indica que la versión recursiva de forma natural es a menudo tan rápido si no más rápido que la versión acumulador, pero no indica las razones por qué. Leí un poco sobre esto y parece que la respuesta es 'tail call optimization/elimination', pero el artículo de Wikipedia parece estar en desacuerdo con lo que dice HtDP, al menos con respecto al rendimiento. ¿Por qué esto es tan?

---

En el trabajo, el estilo recursivo es más rápido. En casa, el estilo del acumulador es más rápido. ¿No hay una heurística general para guiar una elección en cuanto a qué estilo se prefiere generalmente? Entiendo que el estilo de acumulador es más eficiente con la memoria, pero si restringimos la discusión al rendimiento solo, no está claro, al menos para mí, cuál es la mejor opción.

---

He pensado en esto un poco más, y tendría que ponerse de parte de un artículo de Wikipedia sobre la superioridad de la recursividad de estilo acumulador en el caso general . No solo reduce el uso del espacio de pila/montón, el acceso a la memoria siempre estará detrás del acceso de registro y solo se puede hacer más evidente ahora que la multinúcleo está aquí. Aún así, HtDP demuestra que se requieren pruebas reales en todos los casos.

Answer 1

La respuesta dependerá de los detalles del sistema Racket. Aquí está mi opinión sobre esto.

Hay dos diferencias principales entre la versión naturalmente recursiva y la versión de acumulador. En primer lugar, la versión del acumulador está escrita de una manera que permite la optimización de la cola de llamadas. Esto ayuda a acelerar la versión del acumulador, ya que se necesitan crear menos montones de pila. Pero eso es lo contrario de lo que se discute en HtDP y que has visto en tu computadora de trabajo.

La otra diferencia es el orden de multiplicación. La versión múltiplos naturalmente recursivas los números de 1 a 20 en orden ascendente, que es

((((1 * 2) * 3) * … * 19) * 20) 

La versión acumulador multiplica los mismos números en orden descendente, es decir

((((20 * 19) * 18) * … * 2) * 1) 

Matemáticamente, estos son los mismos , y las dos funciones factoriales darán el mismo resultado. No obstante, esta diferencia puede importar.En particular, en cualquier multiplicación intermedia, el resultado intermedio será mayor para este último cálculo que para el cálculo anterior.

El factorial de 20 es un número grande. No cabe en un entero de 32 bits. Eso significa que la raqueta necesitará usar un entero de longitud arbitraria (un "bignum") para representar la respuesta y algunos de los resultados intermedios. La aritmética de precisión arbitraria, incluida la multiplicación que implica bignums, es más lenta que la aritmética de precisión fija.

Dado que los resultados intermedios en la versión del acumulador son siempre mayores que los de la versión recursiva natural, la versión del acumulador requerirá un bignum antes que la versión recursiva. En resumen, aunque ambas versiones requieren el mismo número de multiplicaciones, la versión del acumulador requiere más multiplicaciones de precisión arbitrarias. Esto hace que la versión del acumulador sea más lenta. Aparentemente, el costo adicional de la aritmética supera el ahorro de la reducción de la cantidad de marcos de pila.

¿Por qué no aparecería la misma tendencia en la computadora de su casa? Dijiste que era un Intel iMac, por lo que probablemente sea un sistema de 64 bits. ¡Mientras 20! es un número grande, es pequeño en comparación con lo que cabrá en un entero de 64 bits, por lo que la computadora de su hogar no está haciendo ninguna aritmética de precisión arbitraria y el orden no importa. HtDP tiene la edad suficiente para usar un sistema de 32 bits, al igual que Windows XP en su computadora de trabajo.

más útil para explorar las diferencias sería una función que calcula el producto de una lista de números, ya sea

(define (product numlist) 
    (* (car numlist) (product (cdr numlist))) 

o una versión acumulador. Luego puede ingresar los números en orden ascendente o descendente, independientemente de si usa un enfoque recursivo o basado en acumuladores.

Answer 2

No conozco los inicios del compilador de Racket, pero voy a especular.

Las llamadas de cola son generalmente más caras que las llamadas normales (esto es cierto en .NET, hasta 7 veces más lento), pero en algunos casos la llamada de cola se puede eliminar y termina siendo un loop de estilo C while(1) { ... } por lo tanto, no habrá llamadas adicionales para realizar, simplemente un salto local, eliminando de manera efectiva la sobrecarga de la aplicación de procedimiento.

Answer 3

Un buen compilador convertiría la fac recursiva en una cola recursiva. Entonces no debería haber diferencia en el código compilado.

Answer 4

Muchos buenos puntos de arriba. Me encanta el análisis de lo que debería ser versus por qué no lo hizo. Ese es el material del éxito del Proyecto Euler. Demasiado pronto, un viaje desde Fixnums puede ser problemático.

La secuencia de números se puede multiplicar de mayor a menor o viceversa. También tenemos el comando 'do' que hace la iteración directamente y de manera similar.

(define (hecho n) (si (= n 1) 1 (* n (hecho de (- n 1)))))

(define (fact1 n) (hacer ([nn (- n 1)] [p 1 (* pn)]) ((= n 1) p)))

(define (fact2 n) (do ([i 1 (+ i 1)] [p 1 (* pi)]) ((< ni) p))

(define (fact3 n) (let f ((nn) (p 1)) (if (= n 1) p (f (- n 1) (* pn)))))

(define (fact4 n) (let f ((i 1) (p 1)) (if (< ni) p (f (+ i 1) (* pi)))))