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.Implémenter fibonacci dans Clojure en utilisant la carte/réduire
Répondre
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).
Cela peut-il aider si vous avez utilisé memoize? – Ralph
@Ralph - pas vraiment dans ce cas puisque la fonction est appelée avec des valeurs différentes à chaque fois. Memoise aiderait bien sûr beaucoup si vous utilisiez une implémentation récursive .... – mikera
Pas mal! J'ai fait '(time (fib 10000))' en utilisant votre implémentation et il s'exécute en 71 msec (MacBook Pro 2.66 GHz i7). – Ralph
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)))
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))
- 1. fibonacci en utilisant fork() dans le processus enfant
- 2. Fibonacci utilisant SBN dans OISC en langage machine
- 3. Clojure-problème en utilisant javax.sound.midi.Sequencer
- 4. Comment implémenter lambda comme une fonction appelée "lambda" dans Clojure?
- 5. Implémenter la méthode "intersection" en utilisant java
- 6. Parse error dans la mise en œuvre simple, Haskell Fibonacci
- 7. séquence Fibonacci
- 8. Développement de la série Fibonacci dans VB
- 9. C dans la séquence de Fibonacci
- 10. Fibonacci, binaire ou tas binomial dans C#?
- 11. Fibonacci extension dans C++ segfaulting
- 12. Demandes http Clojure utilisant java.net.URLConnection?
- 13. Comment créer une séquence Fibonacci en Java
- 14. Fibonacci Heap Issue
- 15. Résoudre la séquence Fibonacci Renvoyer récursivement vide dans la fonction
- 16. comment implémenter la recherche élastique en utilisant Java?
- 17. algorithme pour k-Fibonacci
- 18. Seqs Mutable dans clojure
- 19. NHibernate - Implémenter la requête "NOT IN" en utilisant ICriteria
- 20. Comment implémenter la pagination en utilisant un tableau HTML?
- 21. Générateur Python Fibonacci
- 22. Comment faire de l'animation en utilisant swing et clojure?
- 23. Implémenter la fonction Combiner en utilisant les modèles
- 24. Comment implémenter l'analyse en utilisant la priorité des opérateurs?
- 25. comment implémenter la manipulation d'image 3D en utilisant Silverlight?
- 26. Comment implémenter l'adressage WS en utilisant WCF?
- 27. Redéfinir "def" dans Clojure
- 28. Comment implémenter un 'FileUploadCommand' en utilisant OpenFileDialog dans Silverlight?
- 29. Comment implémenter openID en utilisant openid4java dans GSP
- 30. Résoudre récursion dans les nombres de fibonacci
BTW, ce incité cette question lisait "Land of Lisp" par Conrad Barski, MD. Dans son chapitre sur les macros, il met en garde contre leur surutilisation et propose des alternatives en utilisant 'map' et' reduce'. J'ai pensé ... – Ralph