Как улучшить этот кусок кода?

Question

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

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

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

Answer 1

В упражнении вам предлагается написать две функции, одна из которых вычисляет 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 2

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

Answer 3

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

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

Answer 4

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

Answer 5

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

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

Answer 6

Другими словами:

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

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

Версия Джереми Рутена 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)))