Implémenter fibonacci dans Clojure en utilisant la carte/réduire

Question

Est-il possible d'implémenter la série de fibonacci dans Clojure efficacement en utilisant reduce? Que contiendrait "l'accumulateur"? J'imagine qu'il faudra être paresseux. Il est évident de le faire en utilisant récursion ou loop/recur.

Answer 1

On peut utiliser une paire de valeurs de Fibonacci successifs que l'accumulateur, comme suit:

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

Ceci ne soit pas particulièrement efficace en raison de la création d'un bon nombre de paires intermédiaires et l'utilisation de la séquence de gamme superflu pour conduire le bon nombre d'itérations, mais c'est O (n) d'un point de vue algorithmique (c'est-à-dire la même chose que la solution itérative efficace, et bien meilleure que la solution récursive naïve).

Answer 2

L'utilisation de la fonction map/reduce n'est pas utilisée, mais iterate permet d'éviter la récursivité.

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

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

Cela prend 21ms sur un processeur Intel 2,4 Ghz

Sur la même machine, réduire prend 61msec. Je ne sais pas pourquoi itérer est plus rapide.

(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

Cela vous donnera un vecteur des 1000 premiers nombres de Fibonacci (taille de range + 2), gérer le second argument de la fonction (range) que le compteur:

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