Comment améliorer ce morceau de code?

Question

Ma solution 1.11 de SICP est:

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

Comme prévu, une évaluation telle que (f 100) prend beaucoup de temps. Je me demande s'il y avait un moyen d'améliorer ce code (sans pour autant renoncer à la récursion), et / ou de tirer profit de la boîte à noyaux multiples. J'utilise '-système mit'.

Answer 1

Je ne sais pas la meilleure façon de coder dans le schéma, mais une technique commune pour améliorer la vitesse sur quelque chose comme ceci serait d'utiliser memoization . En un mot, l'idée est de mettre en cache le résultat de f (p) (peut-être pour chaque p vu, ou peut-être les n dernières valeurs) afin que la prochaine fois que vous appelez f (p), est retourné le résultat enregistré, plutôt que d'être recalculés. En général, le cache serait une carte d'un tuple (représentant les arguments d'entrée) au type de retour.

Answer 2

L'exercice vous dit d'écrire deux fonctions, qui calcule f « au moyen d'un processus récursif », et un autre qui calcule f « au moyen d'un processus itératif ». Vous avez fait une récursive. Étant donné que cette fonction est très similaire à la fonction fib donnée dans les exemples de la section que vous lié à, vous devriez être capable de comprendre cela en regardant les exemples récursives et itératives de la fonction 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))))

Dans ce cas, vous définir une fonction f-iter qui prendrait a, b et arguments de c ainsi qu'un argument count.

Voici la fonction f-iter. Remarquez la similitude avec fib-iter:

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

Et par un petit essai et erreur, je trouve que a, b et c doivent être initialisées à 2, 1 et 0 respectivement, qui suit également le modèle de la fonction fib initialisation a et b à 1 et 0. Alors f ressemble à ceci:

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

Note: f-iter est encore récursive fonction mais à cause de la façon dont le schéma fonctionne, il fonctionne comme un processus itératif et fonctionne en temps de O(n) et de l'espace de O(1), contrairement à votre le code qui est non seulement une fonction récursive, mais un processus récursif. Je crois que c'est ce que l'auteur de l'exercice 1.1 cherchait.

Answer 3

Eh bien, si vous me demandez, penser comme un mathématicien. Je ne peux pas lire système, mais si vous codez une fonction de Fibonacci, au lieu de définir récursive, résoudre la récurrence et de définir avec une forme fermée. Pour la suite de Fibonacci, la forme fermée se trouve par exemple. Ce sera beaucoup plus rapide.

edit: oups, n'a pas vu que vous avez dit renoncer à se débarrasser de la récursion. Dans ce cas, vos options sont beaucoup plus limitées.

Answer 4

Voir cet article pour un bon tutoriel sur le développement d'une fonction rapide Fibonacci avec la programmation fonctionnelle. Il utilise Common Lisp, ce qui est légèrement différent du schéma dans certains aspects, mais vous devriez être en mesure de vous en tirer avec elle. Votre mise en œuvre est équivalente à la fonction bogo-fig près du haut du fichier.

Answer 5

Pour d'autres termes:

Pour récursion de queue, l'appel récursif doit être la dernière chose que la procédure fait.

Vos appels récursifs sont intégrés dans les * et + expressions, de sorte qu'ils ne sont pas des appels queue (depuis le * et + sont évaluées après l'appel récursif.)

La version de Jeremy Ruten de f-iter est récursive plutôt que itérative (à savoir qu'il ressemble à une procédure récursive mais est aussi efficace que l'équivalent itératif.)

Cependant, vous pouvez faire l'itération explicite:

(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

Cet exercice particulier peut être résolu en utilisant la récursivité queue - au lieu d'attendre pour chaque appel récursif pour revenir (comme cela est le cas dans la solution simple vous présente), vous pouvez accumuler la réponse dans un paramètre, de telle sorte que la récursion se comporte exactement comme une itération en termes de l'espace qu'il consomme. Par exemple:

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