[Haskell-cafe] Another optimization question
anton muhin
antonmuhin at gmail.com
Sat May 17 13:52:05 EDT 2008
On Sat, May 17, 2008 at 8:19 PM, Jeroen <yrn001 at gmail.com> wrote:
> 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?
Just a thought: in your first approach you compare any element of the
list once. In second---twice: once to check if <= x and second time
to check if it is equal to x. That's a hypothesis, but another
implementation of isPrime:
isPrime x = (== x) $ head $ dropWhile (< x) primes
seems to behave closer to your first version than to the second. Note
that that does unnecessary comparison as well the find first element
>= x.
yours,
anton.
More information about the Haskell-Cafe
mailing list