Wie kann ich diesen Code verbessern?

Question

My Lösung von exercise 1.11 SICP ist:

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

wie erwartet eine Auswertung wie (f 100) eine lange Zeit in Anspruch nimmt. Ich habe mich gefragt, ob es einen Weg gibt, diesen Code zu verbessern (ohne auf die Rekursion zu verzichten) und/oder die Multi-Core-Box zu nutzen. Ich benutze 'Mit-Schema'.

Answer 1

Ich bin mir nicht sicher, wie man es am besten in Scheme, aber eine übliche Technik, um die Geschwindigkeit auf etwas wie dies zu verbessern wäre memoization zu verwenden. Kurz gesagt besteht die Idee darin, das Ergebnis von f (p) zwischenzuspeichern (möglicherweise für jedes gesehene p oder möglicherweise die letzten n Werte), so dass beim nächsten Aufruf von f (p) das gespeicherte Ergebnis zurückgegeben wird neu berechnet. Im Allgemeinen wäre der Cache eine Zuordnung von einem Tupel (das die Eingabeargumente repräsentiert) zum Rückgabetyp.

Answer 2

Siehe this article für ein gutes Tutorial zur Entwicklung einer schnellen Fibonacci-Funktion mit funktionaler Programmierung. Es verwendet Common LISP, das in einigen Aspekten etwas von Schema abweicht, aber Sie sollten damit zurecht kommen. Ihre Implementierung entspricht der Funktion bogo-fig am oberen Rand der Datei.

Answer 3

Die Übung sagt Ihnen, zwei Funktionen zu schreiben, eine, die f "mittels eines rekursiven Prozesses" berechnet, und eine andere, die f "mittels eines iterativen Prozesses" berechnet. Du hast das Rekursive getan. Da diese Funktion in die fib Funktion in den Beispielen des Abschnitts, der Sie verknüpfen gegeben sehr ähnlich ist, sollten Sie in der Lage sein, dies an dem rekursiven von der Suche, um herauszufinden, und iterativen Beispiele für die fib Funktion:

; 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 In diesem Fall würden Sie eine f-iter Funktion definieren, die a, b und c Argumente sowie ein count Argument würde.

Hier ist die f-iter Funktion. Beachten Sie die Ähnlichkeit mit fib-iter:

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

Und durch einen kleinen Versuch und Irrtum, ich fand, dass a, b und c-2 initialisiert werden soll, 1 und 0 jeweils, die auch das Muster der fib folgt Funktionsinitialisierung a und b zu 1 und 0. So sieht f wie folgt aus:

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

Hinweis: f-iter ist immer noch eine rekursive Funktion sondern wegen der Art und Weise Schema funktioniert, wird es als iterativer Prozess und läuft in O(n) Zeit und O(1) Raum, im Gegensatz zu Ihrem Code, der nicht nur eine rekursive Funktion, sondern ein rekursiver Prozess ist. Ich glaube, das ist es, wonach der Autor von Übung 1.1 gesucht hat.

Answer 4

Nun, wenn Sie mich fragen, denken Sie wie ein Mathematiker. Ich kann das Schema nicht lesen, aber wenn Sie eine Fibonacci-Funktion kodieren, statt sie rekursiv zu definieren, lösen Sie die Wiederholung und definieren Sie sie mit einer geschlossenen Form. Für die Fibonacci-Sequenz kann die geschlossene Form zum Beispiel here gefunden werden. Das wird viel schneller sein.

edit: oops, habe nicht gesehen, dass du gesagt hast, dass man die Rekursion los wird. In diesem Fall sind Ihre Optionen viel begrenzter.

Answer 5

es anders auszudrücken:

Endrekursion zu erhalten, hat der rekursive Aufruf das allerletzte, was die Prozedur tut sein.

Ihre rekursive Anrufe werden innerhalb der eingebetteten * und + Ausdrücke, so dass sie nicht Endrekursion (da die * und + sind nach der rekursive Aufruf ausgewertet.)

Jeremy Ruten Version von f-iter ist Schwanz- rekursiv statt iterative (dh es sieht aus wie eine rekursive Prozedur, aber so effizient wie die iterative entspricht.)

auch immer Sie die Iteration explizit machen:

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

oder

(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

Diese besondere Übung kann mit Endrekursion gelöst werden - anstatt für jeden rekursiven Aufruf des Warten zurückzukehren (wie es der Fall in der einfachen Lösung ist es, Sie präsentieren), können Sie die Antwort in einem akkumulieren Parameter, so dass sich die Rekursion genau so verhält wie eine Iteration in Bezug auf den Platz, den sie verbraucht. Zum Beispiel:

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