Cómo mejorar este pedazo de código?

Question

Mi solución 1,11 de SICP es:

(define (f n)
  (if (< n 3)
   n
   (+ (f (- n 1)) (* 2 (f (- n 2))) (* 3 (f (- n 3))))
   ))

Como era de esperar, una evaluación tal como (f 100) tarda mucho tiempo. Me preguntaba si había una manera de mejorar el código (sin renunciar a la recursividad), y / o tomar ventaja de la caja de múltiples núcleos. Estoy usando 'esquema-mit'.

Answer 1

No estoy seguro de cuál es la mejor para codificarlo en el esquema, pero una técnica común para mejorar la velocidad en algo como esto sería el uso de memoization . En pocas palabras, la idea es almacenar en caché el resultado de f (p) (posiblemente para cada p visto, o posiblemente los últimos valores n) para que la próxima vez que llame f (p), se devuelve el resultado guardado, en lugar de estar recalculado. En general, la memoria caché sería un mapa de una tupla (que representa los argumentos de entrada) para el tipo de retorno.

Answer 2

El ejercicio le dice a escribir dos funciones, una que calcula f "por medio de un proceso recursivo", y otro que calcula f "por medio de un proceso iterativo". Hiciste una recursiva. Dado que esta función es muy similar a la función fib dada en los ejemplos de la sección que está conectado, usted debería ser capaz de resolver esto al mirar los ejemplos recursivas e iterativas de la función fib:

; Recursive
(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                 (fib (- n 2))))))

; Iterative
(define (fib n)
  (fib-iter 1 0 n))

(define (fib-iter a b count)
  (if (= count 0)
      b
      (fib-iter (+ a b) a (- count 1))))

En este caso, debe definir una función f-iter que tendría a, b, y los argumentos c, así como un argumento count.

Esta es la función f-iter. Nótese la similitud con fib-iter:

(define (f-iter a b c count)
  (if (= count 0)
      c
      (f-iter (+ a (* 2 b) (* 3 c)) a b (- count 1))))

Y a través de un poco de ensayo y error, he encontrado que a, b y c deben ser inicializados a 2, 1 y 0 respectivamente, que también sigue el patrón de la función fib inicializar a y b a 1 y 0. Así f se ve así:

(define (f n)
  (f-iter 2 1 0 n))

Nota: f-iter sigue siendo un función recursiva pero debido a la forma en que funciona el esquema, se ejecuta como un proceso iterativo y se ejecuta en tiempo O(n) y el espacio O(1), a diferencia de su código que no es sólo una función recursiva, sino un proceso recursivo. Creo que esto es lo que el autor de Ejercicio 1.1 buscaba.

Answer 3

Bueno, si me preguntas, pensar como un matemático. No puedo leer esquema, pero si usted está de codificación en función de Fibonacci, en lugar de definir de forma recursiva, resolver la recurrencia y definirlo con una forma cerrada. Para la secuencia de Fibonacci, la forma cerrada se puede encontrar aquí por ejemplo. Eso va a ser mucho más rápido.

editar: ¡Uy, no se ve que usted ha dicho renunciar a deshacerse de la recursividad. En ese caso, sus opciones son mucho más limitadas.

Answer 4

este artículo para un buen tutorial sobre el desarrollo de una función de Fibonacci rápida con la programación funcional. Utiliza Common LISP, que es ligeramente diferente del Esquema en algunos aspectos, pero usted debe ser capaz de salirse con la suya. Su aplicación es equivalente a la función bogo-fig cerca de la parte superior del archivo.

Answer 5

Para decirlo de otra manera:

Para obtener la recursión de cola, la llamada recursiva tiene que ser la última cosa que hace el procedimiento.

Sus llamadas recursivas están integrados dentro de las expresiones y * +, por lo que no son llamadas de cola (ya que el * + y se evalúan después la llamada recursiva.)

versión

de Jeremy Ruten de f-iter es recursiva de cola en lugar de iterativo (es decir, se ve como un procedimiento recursivo pero es tan eficiente como el equivalente iterativo.)

Sin embargo, puede hacer que la iteración explícita:

(define (f n)
  (let iter
    ((a 2) (b 1) (c 0) (count n))
    (if (<= count 0)
      c
      (iter (+ a (* 2 b) (* 3 c)) a b (- count 1)))))

o

(define (f n)
  (do
    ((a 2 (+ a (* 2 b) (* 3 c)))
     (b 1 a)
     (c 0 b)
     (count n (- count 1)))
    ((<= count 0) c)))

Answer 6

Ese ejercicio en particular se puede resolver mediante el uso de la recursión de cola - en lugar de esperar a que cada llamada recursiva para volver (como es el caso en la solución directa que está presente), se puede acumular la respuesta en un parámetro, de tal manera que la recursividad se comporta exactamente igual que una iteración en términos del espacio que consume. Por ejemplo:

(define (f n)
  (define (iter a b c count)
    (if (zero? count)
        c
        (iter (+ a (* 2 b) (* 3 c))
              a
              b
              (- count 1))))
  (if (< n 3)
      n
      (iter 2 1 0 n)))