CODEWITHSUNDEEP
performancelisthaskell
Frank
Frank

Reputation: 4461

Performance comparison of two implementations of a primes filter

I have two programs to find prime numbers (just an exercise, I'm learning Haskell). "primes" is about 10X faster than "primes2", once compiled with ghc (with flag -O). However, in "primes2", I thought it would consider only prime numbers for the divisor test, which should be faster than considering odd numbers in "isPrime", right? What am I missing?

isqrt :: Integral a => a -> a  
isqrt = floor . sqrt . fromIntegral

isPrime :: Integral a => a -> Bool  
isPrime n = length [i | i <- [1,3..(isqrt n)], mod n i == 0] == 1

primes :: Integral a => a -> [a]  
primes n = [2,3,5,7,11,13] ++ (filter (isPrime) [15,17..n])

primes2 :: Integral a => a -> [a]  
primes2 n = 2 : [i | i <- [3,5..n], all ((/= 0) . mod i) (primes2 (isqrt i))]

Upvotes: 2

Views: 211

Answers (2)

jon_darkstar
jon_darkstar

Reputation: 16768

I like what Dietrich has done with the memoization, but I think theres a data structure issue here too. Lists are just not the ideal data structure for this. They are, by necessity, lisp style cons cells with no random access. Set seems better suited to me.

import qualified Data.Set as S

sieve :: (Integral a) => a -> S.Set a
sieve top = let l = S.fromList (2:3:([5,11..top]++[7,13..top]))
                 iter s c
                    | cur > (div (S.findMax s) 2) = s
                    | otherwise = iter (s S.\\ (S.fromList [2*cur,3*cur..top])) (S.deleteMin c)
                    where cur = S.findMin c
             in iter l (l S.\\ (S.fromList [2,3]))

I know its kind of ugly, and not too declarative, but it runs rather quickly. Im looking into a way to make this nicer looking using Set.fold and Set.union over the composites. Any other ideas for neatening this up would be appreciated.

PS - see how (2:3:([5,11..top]++[7,13..top])) avoids unnecessary multiples of 3 such as the 15 in your primes. Unfortunately, this ruins your ordering if you work with lists and you sign up for a sorting, but for sets thats not an issue.

Upvotes: 0

Dietrich Epp
Dietrich Epp

Reputation: 213258

I think what's happening here is that isPrime is a simple loop, whereas primes2 is calling itself recursively — and its recursion pattern looks exponential to me.

Searching through my old source code, I found this code:

primes :: [Integer]
primes = 2 : filter isPrime [3,5..]

isPrime :: Integer -> Bool
isPrime x = all (\n -> x `mod` n /= 0) $
            takeWhile (\n -> n * n <= x) primes

This tests each possible prime x only against the primes below sqrt(x), using the already generated list of primes. So it probably doesn't test any given prime more than once.

Memoization in Haskell:

Memoization in Haskell is generally explicit, not implicit. The compiler won't "do the right thing" but it will only do what you tell it to. When you call primes2,

*Main> primes2 5
[2,3,5]
*Main> primes2 10
[2,3,5,7]

Each time you call the function it calculates all of its results all over again. It has to. Why? Because 1) You didn't make it save its results, and 2) the answer is different each time you call it.

In the sample code I gave above, primes is a constant (i.e. it has arity zero) so there's only one copy of it in memory, and its parts only get evaluated once.

If you want memoization, you need to have a value with arity zero somewhere in your code.

Upvotes: 2

Related Questions