That worked pretty well! It completed in about 9 seconds with the default JVM flags. Better yet I switched to the 64bit server 1.6 VM and it completed in 2.9 seconds. Unlike my code, which threw a stack overflow exception. Sigh.
I *really* appreciate everyone's friendly and helpful feedback. Time permitting I'll dig back into this tonight. On Jul 29, 4:07 am, ataggart <[email protected]> wrote: > 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 -~----------~----~----~----~------~----~------~--~---
