Map/Reduceを使用してClojureにFibonacciを実装します

Question

ClojureでFibonacciシリーズを効率的に使用することは可能ですか reduce？ 「アキュムレータ」には何が含まれていますか？

怠け者でなければならないと思います。再帰またはループ/繰り返しを使用してそれを行う方法は明らかです。

Answer 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）です（つまり、効率的な反復ソリューションと同じです。そして、素朴な再帰的なものよりもはるかに優れています）。

Answer 2

Map/Reduceを使用していませんが、反復は再帰も回避できます。

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

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

これには、Intel 2.4 GHzで21msが必要です

同じマシンで、減速するには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）、関数の2番目の引数を処理する（range）カウンターとして：

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