On 2/10/07, apfelmus@quantentunnel.de
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.