[Haskell-cafe] Another optimization question
Jeroen
yrn001 at gmail.com
Sat May 17 12:19:42 EDT 2008
Hi, I know there's been quite some performance/optimization post lately,
so I hope there still room for one more. While solving a ProjectEuler
problem (27), I saw a performance issue I cannot explain. I narrowed it
down to the following code (never mind that 'primes' is just [1..],
the problem is the same or worse with real primes):
primes :: [Int]
primes = [1..]
isPrime :: Int -> Bool
isPrime x = isPrime' x primes
where isPrime' x (p:ps) | x == p = True
| x > p = isPrime' x ps
| otherwise = False
main = print $ length (filter (== True) (map isPrime [1..5000]))
$ time ./experiment1
5000
real 0m4.037s
user 0m3.378s
sys 0m0.060s
All good, but if I change isPrime to the simpeler
isPrime x = elem x (takeWhile (<= x) primes)
it takes twice as long:
time ./experiment2
5000
real 0m7.837s
user 0m6.532s
sys 0m0.141s
With real primes, it even takes 10 times as long.
I tried looking at the output of ghc -ddump-simpl,
as suggested in a previous post, but it's a bit over
my head (newby here...).
Any suggestions?
Thanks a lot,
Jeroen
More information about the Haskell-Cafe
mailing list