Help with a Shootout program
carsten at codimi.de
Thu Feb 24 09:46:37 EST 2005
On Thu, Feb 24, 2005 at 07:40:49AM -0500, Alson Kemp wrote:
> In order to teach myself Haskell, I've been tinkering with some of
> the Shootout (http://shootout.alioth.debian.org/great/) programs.
> Substantially improved the Mandelbrot program. Then started to work
> on the Spellcheck program, since Haskell seemed to do quite poorly
> at it.
Welcome to the club :-)
> Original program:
> import Data.Set
> main = do
> d <- readFile "Usr.Dict.Words"
> let misspelled x = not $ x `elementOf` (mkSet (lines d))
> interact $ unlines . filter misspelled . Lines
> The original program is nice and short, but uses Set to hold the
> 80,000 word dictionary. The Input file is 80,000 words, too, so I
> figured that searching the Set dictionary would be an O(n^2) task
> (80,000 spellchecks x linear search on 80,000 word dictionary Set).
It's O(n*log n), since a lookup in Data.Set is O(log n).
The O(n^2) version would be
main = do
d <- readFile "Usr.Dict.Words"
interact $ unlines . filter (not . (`elem` (lines d))) . Lines
The real performance problem propbably is not O(n) vs. O(n*log n) but
slow String operations in general. After all, String is a lazy list
of Char. Have a look at the thread mentioned above, possibly Simon's
version has become fast again, otherwise it would be an opportuniy to
reconsider the problems mentioned there.
Carsten Schultz (2:38, 33:47)
PGP/GPG key on the pgp.net key servers,
fingerprint on my home page.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Size: 189 bytes
Desc: not available
Url : http://www.haskell.org//pipermail/glasgow-haskell-users/attachments/20050224/d0529040/attachment.bin
More information about the Glasgow-haskell-users