Mettre en œuvre fibonacci en utilisant Clojure map / reduce

Question

Est-il possible de mettre en œuvre la série de fibonacci dans Clojure efficacement en utilisant reduce? Qu'est-ce que le « accumulateur » contient?

J'imagine qu'il devra être paresseux. Il est évident comment le faire en utilisant récursion ou boucle / RECUR.

Answer 1

Vous pouvez utiliser une paire de valeurs de fibonacci successives 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]

ne tient pas particulièrement efficace pour la création d'un bon nombre de paires intermédiaires et l'utilisation de la séquence de gamme superflue pour entraîner le bon nombre d'itérations, mais il est en O (n) à partir d'un point de vue algorithmique (par exemple le même que l'efficacité solution itérative, et bien mieux que celui récursive naïve).

Answer 2

Ne pas utiliser map / reduce, mais itérer peut éviter récursion aussi.

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