Как улучшить этот фрагмент кода?

Question

Мое решение для упражнение 1.11 of SICP является:

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

Как и ожидалось, такая оценка, как (f 100), занимает много времени.Мне было интересно, есть ли способ улучшить этот код (без отказа от рекурсии) и / или воспользоваться преимуществами многоядерного блока.Я использую "mit-scheme".

Answer 1

Я не уверен, как лучше всего закодировать это в Scheme, но распространенным методом повышения скорости чего-то подобного было бы использовать запоминание.В двух словах, идея состоит в том, чтобы кэшировать результат f (p) (возможно, для каждого просмотренного p или, возможно, для последних n значений), чтобы при следующем вызове f (p) возвращался сохраненный результат, а не пересчитывался.В общем случае кэш будет представлять собой сопоставление кортежа (представляющего входные аргументы) с возвращаемым типом.

Answer 2

В упражнении вам предлагается написать две функции, одна из которых вычисляет f "посредством рекурсивного процесса", и другой, который вычисляет f "посредством итеративного процесса".Вы сделали рекурсивный.Поскольку эта функция очень похожа на fib функция, приведенная в примерах раздела, на который вы ссылаетесь, вы должны быть в состоянии понять это, просмотрев рекурсивные и итеративные примеры 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))))

В этом случае вы бы определили f-iter функция, которая заняла бы a, b, и c аргументы , а также count аргумент.

Вот этот f-iter функция.Обратите внимание на сходство с fib-iter:

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

И путем небольших проб и ошибок я обнаружил, что a, b, и c должен быть инициализирован следующим образом 2, 1, и 0 соответственно, который также следует шаблону fib инициализация функции a и b Для 1 и 0.Итак f выглядит примерно так:

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

Примечание: f-iter все еще является рекурсивным функция но из-за того, как работает схема, она выполняется как итеративная процесс и вбегает в O(n) время и O(1) пробел, в отличие от вашего кода, который является не только рекурсивной функцией, но и рекурсивным процессом.Я полагаю, что это то, что искал автор упражнения 1.1.

Answer 3

Ну, если вы спросите меня, думайте как математик.Я не умею читать схему, но если вы кодируете функцию Фибоначчи, то вместо того, чтобы определять ее рекурсивно, решите рекуррентность и определите ее с помощью замкнутой формы.Для последовательности Фибоначчи замкнутая форма может быть найдена здесь например.Это будет НАМНОГО быстрее.

Редактировать:упс, не видел, что ты сказал об отказе от рекурсии.В этом случае ваши возможности гораздо более ограничены.

Answer 4

Видишь эта статья за хороший учебник по разработке быстрой функции Фибоначчи с помощью функционального программирования.Он использует Common LISP, который в некоторых аспектах немного отличается от Scheme, но вы должны быть в состоянии справиться с этим.Ваша реализация эквивалентна bogo-fig функция находится в верхней части файла.

Answer 5

Иными словами,:

Чтобы получить хвостовую рекурсию, рекурсивный вызов должен быть самым последним, что делает процедура.

Ваши рекурсивные вызовы встроены в выражения * и +, поэтому они не являются конечными вызовами (поскольку вычисляются * и + после рекурсивный вызов.)

Версия Джереми Рутена о f-iter является хвостово-рекурсивным, а не итеративным (т.е.это выглядит как рекурсивная процедура, но столь же эффективна, как итеративный эквивалент.)

Однако вы можете сделать итерацию явной:

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

или

(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

Это конкретное упражнение может быть решено с помощью хвостовой рекурсии - вместо ожидания возврата каждого рекурсивного вызова (как в случае с простым решением, которое вы представляете), вы можете накапливать ответ в параметре таким образом, чтобы рекурсия вела себя точно так же, как итерация, с точки зрения занимаемого пространства.Например:

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