I threw this together, how does it measure up?
(defn prime? [x primes]
(not (first (filter #(zero? (rem x %)) primes))))
(defn next-prime [xs primes]
(lazy-seq
(let [xs (drop-while #(not (prime? % primes)) xs)
prime (first xs)
primes (conj primes prime)]
(cons prime
(next-prime (rest xs) primes)))))
(defn primes []
(next-prime (iterate inc 2) []))
(time (first (drop-while #(< % 100000) (primes))))
On Jul 28, 8:16 pm, 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)))
>
> ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
