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.