clojure - map/reduce を使用して Clojure にフィボナッチを実装する

Question

を使用してClojureでフィボナッチ数列を効率的に実装することは可能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 は使用しませんが、iterate を使用すると再帰も回避できます。

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

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

これには、Intel 2.4 Ghz で 21 ミリ秒かかります

同じマシンで、reduce には 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)))