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.