[Haskell-cafe] Re: Optimization fun
wchogg at gmail.com
Sat Feb 10 17:21:00 EST 2007
On 2/10/07, apfelmus at quantentunnel.de <apfelmus at quantentunnel.de> wrote:
> Creighton Hogg wrote:
> > Hello Haskell-ers,
> > So a friend and I were thinking about making code faster in Haskell, and
> > was wondering if there was a way to improve the following method of
> > generating the list of all prime numbers. It takes about 13 seconds to
> > run, meanwhile my friend's C version took 0.1.
> > I'd love to learn a bit more about how to optimize Haskell code.
> Of course, the best optimization is a better algorithm. In case this is
> what you're after, have a look at
> Colin Runciman, Lazy Wheel Sieves and Spirals of Primes
The glitches may have been unintentional, but the flaw intentionally
> degrades performance: you should not use a strict all' but the lazy
> all prop = foldr (\y z -> prop y && z) True
> from the Prelude. The point is that the lazy version stops inspecting
> the elements of the remaining list whenever (prop y) turns False for the
> first time. This is because && is lazy:
> False && x = False
> for whatever x we supply. For example, take the list
> [True, False, True, True] ++ replicate 100 True
> Here, all returns False after inspecting the first two elements while
> all' inspects every one of the 104 list elements just to return False
> afterwards. As every second number is even, your all' is busy wasting
> time like crazy.
Okay, this is sinking in a good bit better, thank you. I think I've had a
conceptual block about what laziness really means.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Haskell-Cafe