Hi all,
I thought about this naive (it considers even numbers!) implementation of
the sieve:
(defn primes [max]
(let [enqueue (fn [sieve n factor]
(let [m (+ n factor)]
(assoc sieve m
(conj (sieve m) factor))))
next-sieve (fn [sieve candidate]
(if-let [factors (sieve candidate)]
(reduce #(enqueue %1 candidate %2)
(dissoc sieve candidate)
factors)
(enqueue sieve candidate candidate)))]
(apply concat (vals (reduce next-sieve {} (range 2 max))))))
Here the sieve is a map where keys are next known non-primes and values a
list of their prime factors.
It's not lazy and doesn't return a sorted seq but, despite being naive, it
surprisingly doesn't perform that bad:
(time (apply + (primes 100000)))
"Elapsed time: 285.23304 msecs"
454396537
lazy version:
(defn lazy-primes []
(letfn [(enqueue [sieve n factor]
(let [m (+ n factor)]
(assoc sieve m
(conj (sieve m) factor))))
(next-sieve [sieve candidate]
(if-let [factors (sieve candidate)]
(reduce #(enqueue %1 candidate %2)
(dissoc sieve candidate)
factors)
(enqueue sieve candidate candidate)))
(next-primes [sieve candidate]
(if (sieve candidate)
(recur (next-sieve sieve candidate) (inc candidate))
(cons candidate
(lazy-seq (next-primes (next-sieve sieve candidate)
(inc candidate))))))]
(lazy-seq (next-primes {} 2))))
Christophe
On Wed, Jul 29, 2009 at 5:16 AM, Seth <[email protected]> wrote:
>
> I found a simple, worthwhile improvement for a CPU bound
> implementation of the Sieve of Eratosthenes in Clojure and thought I'd
> share it. Also attached are a few metrics and code for the curious.
>
> So I'm using Clojure to solve some of the problems on Project Euler.
> I'd solved some of them before with other languages, but not in new
> lazy/immutable way Clojure is encouraging me to think.
>
> Anyways, my Sieve of Eratosthenes was too slow. It took about three
> minutes on a 2GHz Intel Core Duo MacBook Pro to find the primes lesser
> than 100,000. The blame's on me here -- I'm trying to do it the
> immutable/lazy/??? way rather than the big mutable array way. Patience
> is appreciated as I am still low on the learning curve.
>
> I enabled local jmx monitoring and attached JConsole to the Clojure
> 1.0 process. Almost all the time was spent in garbage collection. JMap
> showed scary things like this:
>
> ================================================================
>
> New Generation (Eden + 1 Survivor Space):
> capacity = 589824 (0.5625MB)
> used = 524288 (0.5MB)
> free = 65536 (0.0625MB)
> 88.88888888888889% used
> Eden Space:
> capacity = 524288 (0.5MB)
> used = 524288 (0.5MB)
> free = 0 (0.0MB)
> 100.0% used
> From Space:
> capacity = 65536 (0.0625MB)
> used = 0 (0.0MB)
> free = 65536 (0.0625MB)
> 0.0% used
> To Space:
> capacity = 65536 (0.0625MB)
> used = 65536 (0.0625MB)
> free = 0 (0.0MB)
> 100.0% used
>
> [...]
>
> ================================================================
>
> So the young spaces are both a.) small and b.) full. Much to my
> surprise enabling parallel garbage collection of the young space was
> the biggest win:
>
> 1.0 = official release
> 1.1a = compiled from git 2009-07-27
>
> * clojure version, jvm flags, seconds to find primes <= 100,000
>
> 1.0, (default), 230
> 1.1a, (default), 190
> 1.1a, -XX:NewRatio=2 -Xmx128m, 148
> 1.1a, -XX:+UseParallelGC, 51
> 1.1a, -XX:NewRatio=2 -Xmx128m -XX:+UseParallelGC, 49
>
> So it looks like my code makes Clojure generate a lot of young
> objects... I tried to stick to the immutable/lazy approach... all
> suggestions would be very welcome -- don't spare the corrections
> please!
>
> ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
>
> (defn subsequent-multiples [val]
> (fn [candidate]
> (or (not= 0 (mod candidate val))
> (= val candidate))))
>
> (defn build-sieve-slow [ceiling]
> (loop [primes ()
> field (range 2 (+ 1 ceiling))]
> (let [cur (first field)
> remnants (filter (subsequent-multiples cur) field)]
> (if (> cur (/ ceiling 2))
> (concat primes remnants)
> (recur
> (concat primes (list (first remnants)))
> (rest remnants))))))
>
> (time (apply + (build-sieve-slow 100000)))
>
> ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
>
> >
>
--
Professional: http://cgrand.net/ (fr)
On Clojure: http://clj-me.blogspot.com/ (en)
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
