Come migliorare questo pezzo di codice?

Question

La mia soluzione a esercizio 1.11 del SICP è:

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

Come previsto, una valutazione come (f 100) richiede molto tempo.Mi chiedevo se esistesse un modo per migliorare questo codice (senza rinunciare alla ricorsione) e/o sfruttare il box multi-core.Sto usando "mit-scheme".

Answer 1

Non sono sicuro il modo migliore per codificare in Scheme, ma una tecnica comune per migliorare la velocità su una cosa del genere sarebbe quella di utilizzare Memoizzazione . In poche parole, l'idea è di memorizzare nella cache il risultato di f (p) (possibilmente per ogni p visto, o forse gli ultimi valori n) in modo che la prossima volta che si chiama f (p), il risultato salvato viene restituito, invece di essere ricalcolato. In generale, la cache sarebbe una mappa da una tupla (che rappresenta i parametri di ingresso) per il tipo di ritorno.

Answer 2

L'esercizio dice di scrivere due funzioni, quella che calcola f "per mezzo di un processo ricorsivo", e un altro che calcola f "per mezzo di un processo iterativo". Hai fatto quello ricorsiva. Dal momento che questa funzione è molto simile alla funzione fib data negli esempi della sezione si è collegato al, si dovrebbe essere in grado di capirlo, cercando in esempi ricorsive e iterative della funzione 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))))

In questo caso si potrebbe definire una funzione f-iter che avrebbe preso a, b, e gli argomenti c così come un argomento count.

Questa è la funzione di f-iter. Si noti la somiglianza 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))))

E attraverso un po 'di tentativi ed errori, ho scoperto che a, b, e c dovrebbero essere inizializzati a 2, 1, e 0 rispettivamente, che segue anche il modello della funzione fib inizializzazione a e b a 1 e 0. Così f assomiglia a questo:

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

Nota: f-iter è ancora un ricorsiva Funzione , ma a causa del modo in cui funziona Scheme, viene eseguito come un iterativo processo e viene eseguito in tempo O(n) e nello spazio O(1), a differenza tua codice che non è soltanto una funzione ricorsiva ma un processo ricorsivo. Credo che questo è ciò che l'autore di Esercizio 1.1 stava cercando.

Answer 3

Beh, se mi chiedete, pensare come un matematico. Non riesco a leggere schema, ma se si sta codifica una funzione di Fibonacci, invece di definire in modo ricorsivo, di risolvere la ricorrenza e definirlo con una forma chiusa. Per la sequenza di Fibonacci, la forma chiusa possono essere trovate qui per esempio. Che sarà molto più veloce.

modifica: oops, non vedi che hai detto rinunciando sbarazzarsi della ricorsione. In tal caso, le opzioni sono molto più limitate.

Answer 4

questo articolo per un buon tutorial per sviluppare una funzione di Fibonacci veloce con la programmazione funzionale. Esso utilizza LISP comune, che è leggermente diverso da Scheme in alcuni aspetti, ma si dovrebbe essere in grado di cavarsela con esso. L'implementazione è equivalente alla funzione bogo-fig vicino alla parte superiore del file.

Answer 5

Per dirla in un altro modo:

Per ottenere la ricorsione in coda, la chiamata ricorsiva deve essere l'ultima cosa che fa la procedura.

Le tue chiamate ricorsive sono incorporate nelle espressioni * e +, quindi non sono chiamate in coda (poiché * e + vengono valutate Dopo la chiamata ricorsiva.)

La versione di Jeremy Ruten di f-iter è ricorsivo in coda piuttosto che iterativo (cioèsembra una procedura ricorsiva ma è efficiente quanto l'equivalente iterativo.)

Tuttavia puoi rendere esplicita l'iterazione:

(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

Questo esercizio particolare può essere risolto utilizzando coda ricorsione - invece di aspettare per ogni chiamata ricorsiva per ritornare (come avviene nella soluzione diretto ti presenti), è possibile accumulare la risposta in un parametro, in modo che la ricorsione si comporta esattamente come un iterazione in termini di spazio che consuma. Per esempio:

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