Hi Seth, On Jul 28, 2009, at 9:16 PM, Seth 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. A common problem is trying to do old things the new way. Functional programming isn't just about immutability, it's a holistic approach, and that often means new algorithms are in order. I ran into this exact problem a couple years ago when I was learning Haskell and was equally at a loss. In your particular case I think you might want to take a look at the source code in the contrib project which implements a lazy list of primes: http://code.google.com/p/clojure-contrib/source/browse/trunk/src/clojure/contrib/lazy_seqs.clj This is a simplified variation on the complex algorithm discussed in "Lazy Wheel Sieves and Spirals of Primes": http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.55.7096&rep=rep1&type=pdf The short answer is that the way to make algorithms spend less time in the garbage collector is to spend less time creating garbage. :) Unfortunately this advice (which I received a lot learning Haskell) is never helpful. There's no substitute for a better algorithm, but it was a long time before I ran into this algorithm. I'm sorry I don't have great concrete advice for your particular implementation. It doesn't look like a bad attempt to me, just not yet very functional. I bet if you look at the lazy-seqs code above things will come together a little better. Probably it would help to try and implement a lazy list of the Fibonacci sequence before looking at that code, and then maybe try some other mathematical sequences that are a little easier to construct too. Hope that helps a little, — Daniel Lyons --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
