Путь-путь для решения Фибоначчи

Question

Я хотел попробовать выучить Лисп, но очень быстро сдался. Я решил попробовать еще раз. Я смотрю на Задача 2 в Project Euler - найти сумму всех четных чисел Фибоначчи до 4 миллионов.

Я написал следующий код, который работает, но все виды безобразны. Главным среди них является тот факт, что это так медленно - потому что он все время делает наивную рекурсию.

Когда я писал эту программу на Python, я строил список по моим подсчетам и никогда не пересчитывал числа. Я знаю, что мог бы сделать это здесь (как-то), но это не соответствует духу функционального программирования. Я сдался после # 3, когда я достиг предела глубины рекурсии и мне пришлось переписать свой код, чтобы использовать цикл вместо рекурсии.

Итак, я полагаю, мои вопросы:

1. Что такое «правильный, неумелый способ» решить эту проблему?
2. Как вы совмещаете рекурсию и понятие «просто вычислить все» с практическим пределом вычисления всего?
3. Есть ли какие-нибудь рекомендации для изучения lisp кроме The Little Schemer и Project Euler?

А вот и мой код:

 (defun fib(i)
   (if (= i 1)                   ;Could rewrite this as a case statement
     1
     (if (= i 2)
       1
       (+ (fib (- i 1)) (fib (- i 2))))))

 (defun solve(i)
   (let ((f (fib i)))            ;Store result in local variable
     (print f)                   ;For debugging
     (if (< 4000000 f)
       0                         ;return
       (if (= 0 (mod f 2))
         (+ f (solve (+ i 1)))   ;add number
         (solve (+ i 1))))))     ;don't

 (print (solve 1))

Answer 1

http://fare.tunes.org/files/fun/fibonacci.lisp позволяет решить проблему Фибоначчи, постепенно улучшая время и производительность памяти при реализации.

Answer 2

Заметка - это способ кеширования результатов в функцию, чтобы избежать перерасчета промежуточных результатов снова и снова. Под мемоизацией в основном подразумевается первый раз, когда вы вызываете функцию с некоторыми аргументами, вычисляете ответ и возвращаете его, и кешируете этот ответ; для последующих вызовов функции с теми же аргументами просто верните кэшированное значение.

В Лиспе вы можете легко использовать функции высшего порядка и макрос для прозрачного запоминания функции. Clojure имеет memoize в качестве стандартной функции. Также смотрите на странице 65 На Лиспе реализацию Common Lisp memoize. Вот оно в Clojure:

(defn fib-naive [i]
  (if (or (= i 1) (= i 2))
    1
    (+ (fib-naive (- i 1)) (fib-naive (- i 2)))))

(def fib-memo
     (memoize (fn [i]
                (if (or (= i 1) (= i 2))
                  1
                  (+ (fib-memo (- i 1)) (fib-memo (- i 2)))))))

user> (time (fib-naive 30))
"Elapsed time: 455.857987 msecs"
832040
user> (time (fib-memo 30))
"Elapsed time: 0.415264 msecs"
832040
user> 

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

(dorun (map fib-memo (range 1 10000)))

будет достаточно, чтобы позволить вам без проблем выполнить (fib 10000).

(Конкретный вопрос вычисления чисел Фибоначчи недавно появился в списке рассылки Clojure . Там есть решение, основанное на числах Лукаса , которые я не понимаю ни в малейшей степени , но который предположительно в 40 раз быстрее наивного алгоритма.)

Answer 3

Используйте хвостовую рекурсию вместо наивной рекурсии. Большинство реализаций Lisp должны выполнять оптимизацию tailcall; больше нет предела глубины рекурсии.

Помимо этого, попробуйте думать о вещах в терминах списков и абстрактных операций, которые вы можете выполнять над этими списками. Две из наиболее важных операций для рассмотрения:

• фильтр
• сложите

Относительно других ресурсов Лиспа:

• Common Lisp - On Lisp
• Схема - Структура и интерпретация компьютерных программ

UPDATE: Хвост-рекурсивная схема fib Функция:

(define (fib n)
  (fib-tr n 1 0))

(define (fib-tr n next result)
  (cond ((= n 0) result)
        (else (fib-tr (- n 1) (+ next result) next))))

Answer 4

(let ((a 1) (b 1))
  (flet ((nextfib ()
           (prog1 a
             (psetf a b b (+ a b)))))
    (loop for fib = (nextfib)
          while (<= fib 4000000)
          when (evenp fib)
            sum fib)))

Выше определена функция NEXTFIB, которая будет генерировать следующий номер Фибоначчи для каждого вызова. LOOP суммирует четные результаты до предела 4000000.

PROG1 возвращает значение первого из его подвыражений. PSETF устанавливает a и b в «параллель».

Это обычная модель. Есть функция генератора, и она вызывается несколько раз, фильтрует результаты и объединяет их.

Answer 5

Способ решить эту проблему - работать снизу вверх, генерируя каждый член Фибоначчи один за другим, добавляя его к сумме, если она четная, и останавливаясь, как только мы достигнем порога в 4 миллиона. Мой LISP ржавый, поэтому он в psuedocode:

one_prior = 1
two_prior = 1
curr = 2
sum = 0
while curr < 4000000000
  if curr % 2 == 0
    sum = sum + curr
  two_prior = one_prior
  one_prior = curr
  curr = one_prior + two_prior

Answer 6

В дополнение ко всем полезным ответам следующие формулы могут обеспечить еще большую эффективность - вычисление Fn в O (Log (n)) вместо O (2 ^ n). Это должно сочетаться с запоминанием и является прочной основой для решения проблемы:

F(2*n) = F(n)^2 + F(n-1)^2

F(2*n + 1) = ( 2*F(n-1) + F(n) )   *   F(n)

Answer 7

Ответ Данио очень поможет с вопросами производительности.

Вот краткий критик вашего стиля:

 (defun fib(i)
   (if (= i 1) ;//Could rewrite this as a case statement
     1
     (if (= i 2)
       1
       (+ (fib (- i 1)) (fib (- i 2)))
     )
   )
 )

Рефакторинг вложенных IF в COND.

Не ставьте круглые скобки в одну строку.

 (defun solve(i)
   (let ((f (fib i))) ;//Store result in local variable
     (print f) ;//For debugging
     (if (

<p>Using ZEROP is clearer.</p>

<pre>
         (+ f (solve (+ i 1))) ;//add number
         (solve (+ i 1)) ;//Don't

Почему вы кладете эти // в? Точка с запятой, за которой следует пробел, достаточно.

) ) ) ) (распечатать (решить 1))

Ваше последнее заявление PRINT вызывает у меня некоторое подозрение. Вы запускаете эту программу из файла или из REPL? Если вы делаете первое, то вам следует подумать о втором. Если вы сделаете последнее, вы можете просто сказать (решить 1), чтобы получить результат.

Answer 8

Мое понимание "духа лиспа" заключается в том, чтобы отделить себя от любой фиксированной, догматической, застрявшей идеи о духе лиспа и использовать конструкцию лиспа, которая наиболее точно отражает структуру вычислений, необходимую для решения вашей проблемы. Например,

(defun euler2 (&optional (n 4000000))
  (do ((i 1 j)
       (j 2 (+ i j))
       (k 0))
      ((<= n i) k)
    (when (evenp i) (incf k i))))

Если вы настаиваете на рекурсии, вот другой способ:

(defun euler2 (&optional (n 4000000))
  (labels ((fn (i j k) 
             (if (<= n i) k (fn j (+ i j) (if (oddp i) k (+ k i))))))
    (fn 1 2 0)))

Answer 9

Чтобы расширить ответ Данио, в статье http://fare.tunes.org/files/fun/fibonacci.lisp представлены два способа заставить код работать быстрее. Использование прямой рекурсии (хвостовой вызов или нет) является O (2 ^ n) и очень медленным. Сложность в том, что каждое значение вычисляется снова и снова. Вы должны делать вещи по-другому. Две рекомендации:

1. Используйте итеративный подход.

(defun bubble-fib (n)
  (declare (optimize (speed 3) (safety 0) (debug 0)))
  (check-type n fixnum)
  (loop repeat n
  with p = 0 with q = 1
  do (psetq p q
        q (+ p q))
  finally (return p)))

2. Использовать памятку. Это означает, что нужно помнить значения, которые вы видели ранее, и вызывать их, а не пересчитывать. В статье представлен пакет CL, который сделает это, а также некоторый код, чтобы сделать это самостоятельно.

Answer 10

Вот памятная версия. В этом случае, поскольку вы должны вычислять каждое число Фибоначчи, пока не найдете более четырех миллионов, использование решений в закрытой форме не принесет особой пользы.

Этот подход создает лексическую среду через let; создать словарь fib-table и функция fib-memoed в этой среде. Конечным продуктом этого является fib-table, доступный из fib-memoed, но не где-либо еще.

Теперь кикер: поскольку мы должны вычислять fib для последовательных значений, пока не будет выполнено какое-то условие, мы запускаем решатель с fib 1. С этого момента, вычисляя следующую выдумку число включает в себя не более 2 словарных поисков и одно дополнение: O(1) BOOM!

;; memoised fib function: make a hash table, then create                                      
;; the fib function in the lexical scope of the hash table                                    
(let ((fib-table (make-hash-table)))
  (setf (gethash 0 fib-table) 1)
  (setf (gethash 1 fib-table) 1)
  (defun fib-memoed (n)
    (let ((x (gethash n fib-table)))
      (cond ((not (null x))
             x)
            (t
             (let ((y (+ (fib-memoed (- n 1))
                         (fib-memoed (- n 2)))))
               (setf (gethash n fib-table) y)
               y))))))

(defun solve ()
  (let ((maxval 4000000))
    (labels ((aux (i acc)
               (let ((x (fib-memoed i)))
                 (cond ((> x maxval) acc)
                       ((evenp x)
                        (aux (1+ i) (+ x acc)))
                       (t (aux (1+ i) acc))))))
      (aux 1 0))))