Como melhorar este pedaço de código?

Question

A minha solução para exercício 1,11 de SICP é:

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

Como esperado, uma avaliação tais como (f 100) leva um longo tempo. Eu queria saber se havia uma maneira de melhorar este código (sem renunciar a recursão), e / ou tirar proveito da caixa multi-core. Eu estou usando 'mit-esquema'.

Answer 1

Eu não tenho certeza a melhor forma de código-lo no esquema, mas uma técnica comum para melhorar a velocidade em algo como isso seria a utilização de memoization . Em poucas palavras, a idéia é armazenar em cache o resultado de f (p) (possivelmente para cada p visto, ou possivelmente os últimos valores n) para que da próxima vez que você chamar f (p), o resultado salvo é retornado, ao invés de ser recalculada. Em geral, o cache seria um mapa de uma tupla (representando os argumentos de entrada) para o tipo de retorno.

Answer 2

O exercício diz-lhe para escrever duas funções, que calcula f "por meio de um processo recursivo", e outra que calcula f "por meio de um processo iterativo". Você fez a uma recursiva. Uma vez que esta função é muito semelhante à função fib dada nos exemplos da seção é ligada ao, você deve ser capaz de descobrir isso por olhar para os exemplos recursiva e iterativa da função 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))))

Neste caso, você definiria uma função f-iter o que levaria a, b e argumentos c, bem como um argumento count.

Aqui é a função f-iter. Observe a semelhança com fib-iter:

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

E através de um pouco de tentativa e erro, descobri que a, b e c deve ser inicializado para 2, 1 e 0 respectivamente, que também segue o padrão da função fib inicializar a e b para 1 e 0. Então f esta aparência:

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

Nota: f-iter ainda é uma recursiva Função , mas por causa da maneira esquema funciona, ele é executado como um iterativo processo e é executado em tempo O(n) e espaço O(1), ao contrário de seu código que não é apenas uma função recursiva, mas um processo recursivo. Eu acredito que este é o que o autor do Exercício 1.1 estava procurando.

Answer 3

Bem, se você me perguntar, pense como um matemático. Eu não posso ler esquema, mas se você está programando uma função Fibonacci, em vez de defini-la de forma recursiva, resolver a recorrência e defini-lo com uma forma fechada. Para a sequência de Fibonacci, a forma fechada pode ser encontrado aqui por exemplo. Isso vai ser muito mais rápido.

edit: oops, não vi que você disse renunciar se livrar da recursividade. Nesse caso, as opções são muito mais limitadas.

Answer 4

este artigo para um bom tutorial sobre o desenvolvimento de uma função de Fibonacci rápido com programação funcional. Ele usa LISP comum, que é ligeiramente diferente do Esquema em alguns aspectos, mas você deve ser capaz de conviver com ele. Sua implementação é equivalente à função bogo-fig perto do topo do arquivo.

Answer 5

Para colocar de outra forma:

Para obter recursão de cauda, ??a chamada recursiva tem que ser a última coisa que o procedimento faz.

As suas chamadas recursivas são incorporados dentro do * e + de expressões, para que eles não são chamadas de cauda (desde o * e + são avaliadas após a chamada recursiva.)

A versão de Jeremy Ruten de f-iter é cauda-recursivo em vez de iterativo (ou seja, ele se parece com um procedimento recursiva, mas é tão eficiente quanto o equivalente iterativa.)

No entanto, você pode fazer a iteração 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)))))

ou

(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

Isso determinado exercício pode ser resolvido usando cauda recursão - em vez de esperar para cada chamada recursiva para retorno (como é o caso na solução simples você presente), você pode acumular a resposta em um parâmetro, de tal forma que a recursão se comporta exatamente o mesmo que uma iteração em termos de espaço que consome. Por exemplo:

(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)))