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. _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe