Вопрос

Мое решение для упражнение 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".

Это было полезно?

Решение

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

Другие советы

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

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

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

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

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

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

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

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

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

(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)))
Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top