Реализуйте фибоначчи в Clojure с помощью карты / уменьшения

Question

Можно ли реализовать серию FIBONACCI в Clojure эффективно, используя reduce? Какой бы «аккумулятор» содержит?

Я представляю, что ему придется лениться. Очевидно, как сделать это, используя рекурсию или петлю / рецензировать.

Answer 1

Вы можете использовать пару последовательных ценностей Fibonacci в качестве аккумулятора следующим образом:

(reduce 
  (fn [[a b] _] [b (+ a b)])  ; function to calculate the next pair of values
  [0 1]                       ; initial pair of fibonnaci numbers
  (range 10))                 ; a seq to specify how many iterations you want

=> [55 89]

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

Answer 2

Не используя карту / уменьшить, но итерация тоже может избежать рекурсии.

(defn iter [[x y]]
  (vector y (+ x y)))

(nth (iterate iter [0 1]) 10000)

Это занимает 21 мс на Intel 2.4 ГГц

На одной и той же машине уменьшите 61msec. Не уверен, почему проигрывает быстрее.

   (time (reduce 
     (fn [[a b] _] [b (+ a b)])  ; function to calculate the next pair of values
     [0 1]                       ; initial pair of fibonnaci numbers
     (range 10000)))

Answer 3

Это даст вам вектор первых 1000 чисел Фибоначчи (размер range + 2), обрабатывая второй аргумент функции (range) как счетчик:

(reduce 
  (fn [a b] (conj a (+' (last a) (last (butlast a)))))  
  [0 1]                      
  (range 998))