[Haskell-cafe] Re: Optimizing spelling correction program

22 Jun 2009

      On Jun 22, 9:06 pm, Daniel Fischer  wrote:
...
Am Montag 22 Juni 2009 21:31:50 schrieb Kamil Dworakowski:
...
On Jun 22, 6:46 am, Bulat Ziganshin  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!