[Haskell-cafe] Re: Optimizing spelling correction program

[Kamil Dworakowski]

On Jun 22, 9:06 pm, Daniel Fischer <daniel.is.fisc... at web.de> wrote:
> Am Montag 22 Juni 2009 21:31:50 schrieb Kamil Dworakowski:
>
>
>
> > On Jun 22, 6:46 am, Bulat Ziganshin <bulat.zigans... at gmail.com> wrote:
> > > Hello Kamil,
>
> > > Monday, June 22, 2009, 12:01:40 AM, you wrote:
> > > > Right... Python uses hashtables while here I have a tree with log n
>
> > > you can try this pure hashtable approach:
>
> > > import Prelude hiding (lookup)
> > > import qualified Data.HashTable
> > > import Data.Array
> > > import qualified Data.List as List
>
> > > data HT a b = HT (a->Int) (Array Int [(a,b)])
>
> > > -- size is the size of array (we implent closed hash)
> > > -- hash is the hash function (a->Int)
> > > -- list is assoclist of items to put in hash
> > > create size hash list = HT hashfunc
> > >                            (accumArray (flip (:))
> > >                                        []
> > >                                        (0, arrsize-1)
> > >                                        (map (\(a,b) -> (hashfunc a,b))
>
> Typo: should be
>
> map (\(a,b) -> (hashfunc a, (a,b))

Wait! Have you typed that definition into the msg off the top of your
head? :)

I went back to using Strings instead of ByteStrings and with that
hashtable the program finishes in 31.5s! w00t!