Lisp -уровень для решения Фибонаци

Ответ 1

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

Ответ 2

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

В Lisp вы можете легко использовать функции более высокого порядка и макрос, чтобы прозрачно запоминать функцию. Clojure имеет memoize как включенную стандартную функцию. Также смотрите на стр. 65 из В Lisp для общей реализации 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 списке рассылки. Там есть решение, основанное на номера Lucas, которые я ничуть не понимаю, но, предположительно, в 40 раз быстрее, чем наивный алгоритм.)

Ответ 3

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

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

• Вкл 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))))

Ответ 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 в 'parallel'.

Это общий шаблон. Существует функция генератора, и один раз называет ее, фильтрует результаты и объединяет их.

Ответ 5

Способ решения проблемы заключается в том, чтобы работать снизу вверх, генерируя каждый термин Fibonnaci один за другим и добавляя его к сумме, даже если он, и останавливается, как только мы достигнем порога в 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

Ответ 6

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

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

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

Refactor вложенные IFs в COND.

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

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

Using ZEROP is clearer.

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

Why do you put those // in? A semicolon followed by a space is enough.

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

Ответ 7

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

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

(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. Используйте Memoization. Это означает запоминание значений, которые видны ранее, и их повторение, а не пересчет их. В статье представлен пакет CL, который сделает это, а также некоторый код, чтобы сделать это самостоятельно.

Ответ 8

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

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

Ответ 9

В дополнение ко всем полезным ответам следующие формулы могут обеспечить еще большую эффективность - вычисление 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)

Ответ 10

Смотрите как видео, так и текст, расположенный по адресу: http://groups.csail.mit.edu/mac/classes/6.001/abelson-sussman-lectures/

Ответ 11

(defun fib (x &optional (y 0) (z 1))
           (if (< x z)
               nil
               (append (list z) (fib x z (+ y z)))))

CL-USER> (reduce #'+ (remove-if-not #'evenp (fib 1000000)))

Ответ 12

Простой, эффективный способ создания списка чисел фибоначчи:

(defun fibs (n &optional (a 1) (b 1))
  (loop repeat n 
        collect (shiftf a b (+ a b))))

(shiftf) принимает любое количество мест и, наконец, значение. Каждому месту присваивается значение следующей переменной, при этом последняя переменная принимает значение, которое приходит после него. Он возвращает значение первого места. Другими словами, он сдвигает все значения, оставшиеся на один.

Однако вам не нужен полный список (вам нужны только эвены), и вам совсем не нужен этот список (вам нужна только сумма), так что это можно напрямую обработать в функции. Каждое третье число фибоначчи четное, поэтому...

(defun euler-2 (limit &optional (a 1) (b 1))
  (loop for x upfrom 1
        until (> a limit)
        if (zerop (mod x 3)) 
           sum a
        do (shiftf a b (+ a b))))