conj - Implementar fibonacci en Clojure usando map/reduce

list conj clojure

Question

¿Es posible implementar la serie de fibonacci en Clojure de manera eficiente usando reduce ? ¿Qué contendría el "acumulador"?

Imagino que tendrá que ser flojo. Es obvio cómo hacerlo usando recursion o loop / recur.

Answer 1

Puede usar un par de valores sucesivos de Fibonacci como 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 muchos pares intermedios y el uso de la secuencia de rango superfluo para manejar el número correcto de iteraciones, pero es O (n) desde una perspectiva algorítmica (es decir, lo mismo que la solución iterativa eficiente, y mucho mejor que el ingenuo recursivo).

Answer 2

No usar mapa / reducir, pero iterar puede evitar la recursión también.

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

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

Esto lleva 21 ms en Intel 2.4 Ghz

En la misma máquina, reduce lleva 61 mseg. No estoy seguro de por qué iterar 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 del range + 2), manejando 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))