Help with a Shootout program

[Carsten Schultz]

Hi Alson!


On Thu, Feb 24, 2005 at 07:40:49AM -0500, Alson Kemp wrote:
> All,
> 	In order to teach myself Haskell, I've been tinkering with some of
> the Shootout (http://shootout.alioth.debian.org/great/) programs.

Good idea.

> 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 :-)

http://www.mail-archive.com/glasgow-haskell-users@haskell.org/msg06012.html

> 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.

Take care,

Carsten

-- 
Carsten Schultz (2:38, 33:47)
http://carsten.codimi.de/
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
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
Url : http://www.haskell.org//pipermail/glasgow-haskell-users/attachments/20050224/d0529040/attachment.bin