2010/1/27 Christophe Grand <christo...@cgrand.net>: > See > http://clj-me.cgrand.net/2009/07/30/everybody-loves-the-sieve-of-eratosthenes/ > for other impls of the SoE -- there was no transients at the time but > they are fast... and can be transientified.
Oh, that's really cool, Christophe! Very elegant as well as *fast*. Coming to think of it, I might have read it before, as I do read your blog from time to time... would have posted a link had I remembered. Anyway, I've improved my sieve to skip even numbers (added to the aforementioned gist now) and I still find that your lazy-primes3 runs circles around it like crazy. :-) I've also experimented with a very basic deftype / defprotocol based leftist heap implementation and built some wheel sieves on top of that: http://gist.github.com/288471 Still no luck, performance wise (skipping my odd-transient-incremental-sieve, about twice as fast than the lheap version in some runs, but just about the same in others (!?) and apparently faster to run out of space -- couldn't get prime no. 5000000 with it -- *and* still nowhere near as fast as lazy-primes3 in these kinds of runs): user> (let [ps (lazy-primes3)] (time (nth ps 99999))) "Elapsed time: 1844.562708 msecs" 1299709 user> (let [ps (lazy-primes3)] (time (nth ps 999999))) "Elapsed time: 34391.117946 msecs" 15485863 user> (let [ps (lheap-map-incremental-wheel-sieve make-wheel 4)] (time (nth ps 99999))) "Elapsed time: 7926.3331 msecs" 1299709 user> (let [ps (lheap-map-incremental-wheel-sieve make-wheel 4)] (time (nth ps 999999))) "Elapsed time: 116213.155085 msecs" 15485863 That means that lazy-primes3 spent ~19 times as long computing the first million primes than it did computing the first 100000, whereas with lheap-map-incremental-wheel-sieve that factor was ~14. I was hoping for at least a theoretical asymptotic advantage, however, that difference actually seemed to fall off when I experimented with even longer ranges, leading me (again) to the conjecture that my sieves are especially problematic GC-wise... Regrettably, I've got no experience with profiling on the JVM -- I'd be very greatful for any pointers on this. Sincerely, Michal -- 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
