On Tue, Feb 15, 2011 at 1:13 AM, Andreas Kostler
<andreas.koestler.le...@gmail.com> wrote:
> Hi all,
> Does anyone wanna have a look at my solution for Project Euler Problem 28?
>
> (defn diagonal-sum [n-max]
> (+ 1 (reduce +
> (map (fn[n]
> (reduce + (map #(- (* n n) (* % (- n 1))) (range 4))))
> (take-nth 2 (range 3 (+ 2 n-max)))))))
>
> The function does the job. The solution takes about 1.5msec on my machine to
> compute.
I get:
user=> (time (diagonal-sum 1001))
"Elapsed time: 3.18344 msecs"
669171001
You have a 5GHz CPU? Cool.
> I'd like to discuss more performant and/or more idiomatic solutions to that
> problem :)
Step one: move the computation of the square of n out of the inner
reduce, and similarly; e.g.
(defn diagonal-sum-2 [n-max]
(+ 1 (reduce +
(map (fn[n]
(let [n2 (* n n)
n-1 (- n 1)]
(reduce + (map #(- n2 (* % n-1)) (range 4)))))
(take-nth 2 (range 3 (+ 2 n-max)))))))
That might shave off a few ns.
user=> (time (diagonal-sum-2 1001))
"Elapsed time: 3.06176 msecs"
Not much savings, though.
To make this blaze you'll need to kill the HOF use and resort to loop,
recur, and primitives. Using 1.2:
(defn diagonal-sum-3 [n-max]
(let [nm+2 (int (+ 2 n-max))
one (int 1)
two (int 2)
three (int 3)]
(loop [sum one n three]
(if (< n nm+2)
(let [n2 (unchecked-multiply n n)
n-1 (unchecked-dec n)
t1 (unchecked-subtract n2 n-1)
t2 (unchecked-subtract t1 n-1)
t3 (unchecked-subtract t2 n-1)
res (unchecked-add n2
(unchecked-add t1
(unchecked-add t2 t3)))]
(recur
(unchecked-add sum res)
(unchecked-add n two)))
sum))))
user=> (time (diagonal-sum-3 1001))
"Elapsed time: 0.0402 msecs"
669171001
That's a small speedup from moving repeated computations outside the
inner loop but a nearly /hundred-fold/ speedup from going to primitive
arithmetic and unrolling the inner loop.
The only further speedup possible would be to parallelize for multicore CPUs:
(defn diagonal-sum-4a [n-max offset step]
(let [nm+2 (int (+ 2 n-max))
zero (int 0)
step (int step)
offset (int (+ 3 offset))]
(loop [sum zero n offset]
(if (< n nm+2)
(let [n2 (unchecked-multiply n n)
n-1 (unchecked-dec n)
t1 (unchecked-subtract n2 n-1)
t2 (unchecked-subtract t1 n-1)
t3 (unchecked-subtract t2 n-1)
res (unchecked-add n2
(unchecked-add t1
(unchecked-add t2 t3)))]
(recur
(unchecked-add sum res)
(unchecked-add n step)))
sum))))
(defn diagonal-sum-4 [n-max]
(let [cores (.availableProcessors (Runtime/getRuntime))
step (* 2 cores)]
(inc
(reduce +
(map get
(doall
(map #(future (diagonal-sum-4a n-max % step))
(take cores
(iterate #(+ 2 %) 0)))))))))
user=> (time (diagonal-sum-4 1001))
"Elapsed time: 0.21268 msecs"
669171001
About a 4x /slowdown/ on my (dual-core) machine. The overhead from
parallelizing isn't worth it when the job size is only 1001. This
remains true for job sizes up to the maximum that doesn't get b0rked
by unchecked 32-bit arithmetic.
So, go with diagonal-sum-3's implementation. :)
Note: if you use Clojure 1.3 you'll have to make some changes to it.
--
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
