On 2/10/07, [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote:
Creighton Hogg wrote: > Hello Haskell-ers, > So a friend and I were thinking about making code faster in Haskell, and I > 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 http://citeseer.ist.psu.edu/runciman97lazy.html
<snip helpfullness> 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.
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
