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.
pgpHPMFoJaYLE.pgp
Description: PGP signature
_______________________________________________ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users