Re: How to solve Collatz Conjecture problem for huge numbers using clojure parallelism tricks?

[Zack Maril]

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

[Alan Malloy]

(max-key :power mario luigi)

On Thursday, January 31, 2013 6:08:21 PM UTC-8, Leandro Moreira wrote:

Running through this problem I also faced the weird situation, so:

Given two maps

(def mario {:color "red" :power 45})

(def luigi {:color "green" :power 40})

I want the max between both but based on :power key.

It would be something like this.

(max mario luigi)

I expect max return not only 45 but the whole map.... Is there any built in function for that?

[AtKaaZ]

amalloy, inspirational as always! thank you

(max-key :power mario luigi)

--
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clo...@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+u...@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+u...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

--

Please correct me if I'm wrong or incomplete,
even if you think I'll subconsciously hate it.

[Leandro Moreira]

thanks

[Leandro Moreira]

thanks mand