maplo/reduceを使用してClojureでフィボナッチを実装する

Question

を使用してClojureでfibonacciシリーズを効率的に実装できますか？ 「アキュムレータ」には何が含まれますか？

私はそれが怠惰でなければならないと想像します。再帰またはループ/再帰を使用してそれを行う方法は明らかです。

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

これはカウンタとして機能（range）の第2引数を処理し、あなたの最初の1000のフィボナッチ数（range + 2のサイズ）のベクトルを与える：

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