Wdrożenie fibonacci w Clojure przy użyciu mapy/zmniejszyć

Question

Czy możliwe jest wydajne wdrożenie serii fibonacci w Clojure przy użyciu reduce? Co zawierałby "akumulator"?

Wyobrażam sobie, że będzie musiał być leniwy. Jest oczywiste, jak to zrobić, używając rekurencji lub pętli/recur.

Answer 1

Można stosować parę kolejnych wartości Fibonacciego jak akumulator, w następujący sposób:

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

nie jest szczególnie wydajny ze względu na utworzenie wielu par pośrednich, oraz wykorzystania zbędną sekwencji zakresie do pojazdów odpowiednią liczbę iteracji, ale jest to O (n) z perspektywy algorytmicznej (tj. takie samo jak efektywne rozwiązanie iteracyjne, i znacznie lepsze niż naiwna rekursywna).

Answer 2

Nie używając mapy/zmniejszenia, ale iteracja może również zapobiec rekursji.

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

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

ten trwa 21ms na Intel 2.4 GHz

na tej samej maszynie, zmniejszyć trwa 61msec. Nie wiem, dlaczego iteracja jest szybsza.

(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

To daje wektor 1000 pierwszych liczb Fibonacciego (wielkość range + 2), manipulacja drugi argument funkcji (range) jako licznik:

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