Implementieren Sie Fibonacci in Clojure mit Karte/reduzieren

Question

Ist es möglich, die Fibonacci-Serie in Clojure effizient mit reduce zu implementieren? Was würde der "Akkumulator" enthalten?

Ich stelle mir vor, dass es faul sein muss. Es ist offensichtlich, wie man es unter Verwendung von Rekursion oder Schleife/Wiederholung durchführt.

Answer 1

Sie ein Paar von aufeinanderfolgenden Fibonacci-Wert als Akkumulator verwendet werden könnten, wie folgt:

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

dies aufgrund der Bildung von vielen Zwischenpaaren und die Verwendung der überflüssigen Bereich Sequenz nicht besonders effizient zu fahren die richtige Anzahl von Iterationen, aber es ist O (n) aus einer algorithmischen Perspektive (dh dasselbe wie die effiziente iterative Lösung und viel besser als das naive rekursive).

Answer 2

Nicht mit map/reduce, aber iterate kann auch Rekursion vermeiden.

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

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

Dieses 21ms auf einem Intel 2,4 Ghz

Auf der gleichen Maschine nimmt, reduzieren nimmt 61msec. Nicht sicher, warum iterate schneller ist.

(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

Dies wird Ihnen ein Vektor der ersten 1000 Fibonacci-Zahlen (Größe range + 2), das zweite Argument der Funktion (range) als Gegen Handhabung:

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