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))