[Haskell-Cafe] Quick question for a slow program
Daniel Fischer
daniel.is.fischer at web.de
Sat Jun 7 14:27:31 EDT 2008
Am Samstag, 7. Juni 2008 11:26 schrieb Slavomir Kaslev:
> Hello,
>
> I was just brushing my haskell-fu skills writing a solution for Google
>
> Treasure Hunt Problem 4. Hers is what it looks like:
> > primes = sieve [2..]
> > where
> > sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0]
That alone breaks at least three of the tortoise's legs.
Simple trial division:
primes = 2:3:filter isPrime [5,7 .. ]
isPrime n
| n < 2 = False
| n < 4 = True
| even n = False
| otherwise = go (tail primes)
where
r = floor $ sqrt (fromIntegral n + 0.5)
go (p:ps) = (r < p) || (n `mod` p /= 0) && go ps
is orders of magnitude faster. A really good prime generator wins a lot.
> >
> > sumOf n l = sum (take n l) : sumOf n (tail l)
This is also not really good,
sumOf n l = zipWith (-) (drop n sms) sms
where
sms = scanl (+) 0 l
is a bit faster, specialising
primeSums = scanl (+) 0 primes
sumOfPrimes n = zipWith (-) (drop n primeSums) primeSums
a bit more.
I don't see more improvements directly.
> >
> > find l = foldl1 aux l
> > where
> > aux (x:xs) (y:ys) | x == y = x : aux xs ys
> >
> > | x < y = aux xs (y:ys)
> > | x > y = aux (x:xs) ys
> >
> > puzzle = find (reverse [primes, p7, p17, p41, p541])
> > where
> > p7 = sumOf 7 primes
> > p17 = sumOf 17 primes
> > p41 = sumOf 41 primes
> > p541 = sumOf 541 primes
> >
> > main = do mapM (\x -> putStrLn $ show x) puzzle
>
> While the code is quite readable and straight forward it is as slow as
> tortoise with four legs broken. What optimizations would you suggest,
> while still keeping the code clear and highlevel?
>
> Thank you in advance.
>
> Cheers.
More information about the Haskell-Cafe
mailing list