On Sat, May 17, 2008 at 8:19 PM, Jeroen <[EMAIL PROTECTED]> 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. _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
