Implementieren Sie Fibonacci in Clojure Karte unter / reduzieren

Question

Ist es möglich, die Fibonacci-Reihe in Clojure effizient reduce mit implementieren? Was wäre der „Akkumulator“ enthalten?

Ich stelle mir vor, dass es faul sein müssen. Es ist offensichtlich, wie es zu tun mit Rekursion oder Loop / wieder auftreten.

Answer 1

Sie könnten ein Paar aufeinanderfolgender Fibonacci-Wert als Akkumulator verwenden, 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 ist nicht besonders effizient, aufgrund der Erzeugung von vielen Zwischenpaaren und die Verwendung der überflüssigen Bereich Sequenz der richtige Anzahl von Iterationen zu fahren, aber es ist O (n) aus einer algorithmischen Perspektive (dh dasselbe wie die effizienten iterative Lösung, und viel besser als die naive rekursive eins).

Answer 2

Nicht Karte unter / reduzieren, aber Iterierte kann Rekursion zu vermeiden.

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

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

Dieser Vorgang dauert 21ms auf einem Intel 2,4 Ghz

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

   (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 gibt Ihnen einen Vektor der ersten 1000 Fibonacci-Zahlen (Größe range + 2), das zweite Argument der Funktion Handling (range) als Zähler:

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