Take a look at this gist: https://gist.github.com/4688693
It uses memoize to eek out a little bit more performance. λ ~/Projects/experiments/collatz > lein run Compiling collatz.core [9 19] "Elapsed time: 30.236 msecs" [97 118] "Elapsed time: 5.532 msecs" [871 178] "Elapsed time: 22.529 msecs" [6171 261] "Elapsed time: 114.061 msecs" [77031 350] "Elapsed time: 578.955 msecs" [837799 524] "Elapsed time: 3686.937 msecs" [8400511 685] "Elapsed time: 40478.64 msecs" On my machine it is usually significantly faster than when I run the provided code: λ ~/Projects/experiments/collatz > lein run Compiling collatz.core {:n 9, :count 19} "Elapsed time: 22.024 msecs" {:n 97, :count 118} "Elapsed time: 6.838 msecs" {:n 871, :count 178} "Elapsed time: 56.313 msecs" {:n 6171, :count 261} "Elapsed time: 293.266 msecs" {:n 77031, :count 350} "Elapsed time: 962.113 msecs" {:n 837799, :count 524} "Elapsed time: 9529.107 msecs" λ ~/Projects/experiments/collatz > lein run Compiling collatz.core {:n 9, :count 19} "Elapsed time: 28.077 msecs" {:n 97, :count 118} "Elapsed time: 8.1 msecs" {:n 871, :count 178} "Elapsed time: 31.023 msecs" {:n 6171, :count 261} "Elapsed time: 144.956 msecs" {:n 77031, :count 350} "Elapsed time: 944.857 msecs" {:n 837799, :count 524} "Elapsed time: 10030.467 msecs" {:n 8400511, :count 685} "Elapsed time: 113490.494 msecs" Of course, there is a bunch of optimizations you can take mathematically: http://en.wikipedia.org/wiki/Collatz_conjecture -Zack On Friday, February 1, 2013 4:29:53 AM UTC+4, Leandro Moreira wrote: > > The problem is known as Collatz Conjecture (also 3n + 1 conjecture). > Basically given a n number then you apply the following rule. > > If n is even then n/2 otherwise 3 * n + 1, you keep applying this until you > reach the number 1. > For instance, starting with *n = 6*, one gets the sequence 6, 3, 10, 5, 16, > 8, 4, 2, 1. (with *8 items*) > > Now the challenge tell the *n* with n descending from 1000000 to 1 and with > the *greater number of items*. > > Then I did the program bellow (I'm very happy for feedback since I'm totally > noobie to clj), but it takes forever, there is anyway to make it fast? > > (defn- apply-collatz-conjecture > "Given n, it returns n/2 if it's even or n*3+1 if it's odd." > [n] > (if (even? n) > (/ n 2) > (+ (* 3 n) 1))) > > (defn- collatz-conjecture-seq > "Given n, it returns the sequence of collatz-conjecture." > [n] > (loop [n n sequence []] > (if (not= n 1) > (recur (apply-collatz-conjecture n) (cons > (apply-collatz-conjecture n) sequence)) > (reverse sequence)))) > > (defn- collatz-conjecture-number-of-items > "It returns a map with n and number of items on its collatz-conjecture > sequence." > [n] > { :n n :count (count (collatz-conjecture-seq n)) } ) > > (defn- greater > "Given x and y, it returns the element with greater count." > [x y] > (if (> (:count x) (:count y)) > x > y)) > > (defn n-with-more-items > "Given n, it applies collatz-conjecture for the range 1..n > and return the n with more items." > [n] > (reduce greater (pmap collatz-conjecture-number-of-items (range 1 n)))) > > > The only thing I thought was use pmap but it didn't make it super fast. > > *Using only map* > user=> (time (n-with-more-items 999999)) > "Elapsed time: *21191.762883 msecs*" > {:n 837799, :count 524} > > *Using pmap* > user=> (time (n-with-more-items 999999)) > "Elapsed time: *13230.919979 msecs*" > {:n 837799, :count 524} > > Any thoughts on how can I apply parallelism to solve this (especially on > my frustrate try of use map and reduce)? > -- -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups "Clojure" group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.