[Haskell-Cafe] Quick question for a slow program
Dries Harnie
dries at harnie.be
Sat Jun 7 13:58:45 EDT 2008
On Sat, 7 Jun 2008 12:26:17 +0300
"Slavomir Kaslev" <slavomir.kaslev at gmail.com> wrote:
> 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]
> >
> > sumOf n l = sum (take n l) : sumOf n (tail l)
> >
> > 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?
While I can't quite prove it, I surmise find is wasting a lot of time
tracking down numbers which are sums of three or four of those lists before
continuing.
Here's mine:
> sliding n = map (sum . take n) $ tails primes
>
> merge (x:xs) (y:ys) | x < y = x:merge xs (y:ys)
> | otherwise = y:merge (x:xs) ys
>
> four = filter (\l -> length l == 5) $ group $ foldr1 merge $ map sliding [1,5,43,107,689]
In my original implementation I used an isPrime test at the end, but I like
your approach better (hence the 1 in map sliding).
Does this still count as "clear and highlevel"? :)
Dries Harnie
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20080607/f1cb8c99/signature.bin
More information about the Haskell-Cafe
mailing list