Implementar Fibonacci en Clojure en el mapa / reducir

Question

¿Es posible aplicar la serie de Fibonacci en Clojure de manera eficiente utilizando reduce? ¿Cómo sería el "acumulador" contener?

Me imagino que tendrá que ser perezoso. Es obvio cómo hacerlo utilizando la recursividad o bucle / repiten.

Answer 1

Se puede usar un par de valores sucesivos de Fibonacci como el acumulador, de la siguiente manera:

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

Esto no es particularmente eficiente debido a la creación de una gran cantidad de pares intermedios y uso de la secuencia gama superfluo para conducir el número correcto de iteraciones, pero es O (n) desde una perspectiva algorítmica (es decir, la misma que la eficiente solución iterativa, y mucho mejor que el que recursiva naive).

Answer 2

No usar el mapa / reducir, pero iterate puede evitar la repetición también.

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

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

Esto se lleva a 21ms en un 2,4 Ghz Intel

En la misma máquina, reducir la toma 61msec. No sé por qué iterate es más rápido.

   (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

Esto le dará un vector de los primeros 1000 números de Fibonacci (tamaño de range + 2), el manejo el segundo argumento de la función (range) como el contador:

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