Wie dieses Stück Code zu verbessern?

Question

Meine Lösung Übung rel="nofollow 1,11 von 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) dauert eine lange Zeit. Ich frage mich, ob es eine Möglichkeit, diesen Code zu verbessern war (ohne die Rekursion Verzicht) und / oder nutzen Multi-Core-Box. Ich verwende 'mit-Regelung'.

Answer 1

Ich bin nicht sicher, wie sie am besten in Schema zu codieren, aber eine übliche Technik, Geschwindigkeit, wie dies auf etwas zu verbessern würde memoization . Auf dem Punkt gebracht, ist die Idee, das Ergebnis von f (p) (möglicherweise für jeden p gesehen oder möglicherweise die letzten n Werte), so dass beim nächsten Mal, wenn Sie anrufen f (p), das gespeicherte Ergebnis wird zurückgegeben zwischenzuspeichern, anstatt zu sein neu berechnet. Im Allgemeinen würde die Cache eine Karte aus einem Tupel sein (die die Eingabeargumente) mit dem Rückgabetyp.

Answer 2

Die Übung zeigt Ihnen zwei Funktionen zu schreiben, eine, die f „mittels eines rekursiven Prozess“, und eine andere, die f „mittels eines iterativen Prozesses“ berechnet berechnet. Sie haben das rekursive ein. Da diese Funktion in der 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 diesem Fall würden Sie eine f-iter Funktion definieren, die a nehmen würde, b und c Argumente sowie ein count Argument.

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, fand ich, dass a, b und c initialisiert werden sollen, um 2, 1 und 0 verbunden, die auch das Muster der fib Funktion a und b Initialisierung 1 und 0 folgt. So f sieht 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, läuft es als iterativen 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 rekursiven Prozess. Ich glaube, das ist das, was der Autor der Aufgabe 1.1 wurde auf dem Bild.

Answer 3

Nun, wenn Sie mich fragen, denken wie ein Mathematiker. Ich kann nicht Schema lesen, aber wenn Sie eine Fibonacci-Funktion sind Codierung, sondern es rekursiv definieren, lösen die Wiederholung und definieren es mit einer geschlossenen Form. Für die Fibonacci-Folge kann die geschlossene Form hier zum Beispiel zu finden. Das wird viel schneller sein.

edit: oops, nicht sehen, dass Sie sagte Verzicht der Rekursion loszuwerden. In diesem Fall sind Ihre Möglichkeiten viel begrenzter.

Answer 4

Siehe dieser Artikel für ein gutes Tutorial auf eine schnelle Fibonacci-Funktion entwickeln mit der funktionalen Programmierung. Es verwendet Common Lisp, die aus dem Schema in einigen Aspekten ist etwas anders, aber Sie sollten mit ihm auszukommen können. Ihre Implementierung entspricht die bogo-fig Funktion in der Nähe des Anfangs der Datei.

Answer 5

Um es anders auszudrücken:

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

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

Jeremy Ruten Version von f-iter ist tail-rekursive anstatt iterative (das heißt es wie eine rekursive Prozedur sieht aber so effizient wie die iterative entspricht.)

Sie können jedoch die Iteration machen deutlich:

(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

Die besondere Übung kann mit Endrekursion gelöst werden - anstatt zu warten, für jeden rekursiven Aufruf zurückzukehren (wie es der Fall in der einfachen Lösung, die Sie vorhanden ist), können Sie die Antwort in einem Parameter, so sammeln sie, dass die Rekursion verhält sich genau das gleiche wie eine Iteration in Bezug auf den Raum, 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)))