Внедрение фибоначчи в Clojure с помощью map/reduce

Можно ли эффективно реализовать серию фибоначчи в Clojure с помощью reduce? Что будет содержать "аккумулятор"?

Я полагаю, что это должно быть лениво. Это очевидно, как это сделать, используя рекурсию или цикл/recur.

Ответ 1

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

(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) с алгоритмической точки зрения (то же самое, что и эффективная итеративное решение и намного лучше наивного рекурсивного).

Ответ 2

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

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

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

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

На той же машине сокращение занимает 61 мсек. Не уверен, почему итерация выполняется быстрее.

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

Ответ 3

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

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