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 [email protected]
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
[email protected]
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 [email protected].
For more options, visit https://groups.google.com/groups/opt_out.
