[Haskell-cafe] can there be (hash-table using) O(n) version of
this (I think currently) n log n algo?
Thomas Hartman
tphyahoo at gmail.com
Sat Jul 18 11:23:10 EDT 2009
Thanks Bulat.
FWIW, i take it that
http://www.haskell.org/haskellwiki/Shootout/Knucleotide
is what Edward was referring to, with the shootouts. It seems that a
lot of progress has been made but not much has been migrated back to
hackage.
Going back to my original question, I am now looking for a dead simple
motivating example for showing the example of using a (good) hashtable
over Data.Map, with a tangible demo of O(n) over O(n log n) running
times. I mean, something where running an input of (10^4) size versus
(10^6) size shows a noticeably laggier run when using Set versus
hashtable.
I don't think maybe my original example quite qualifies because I
think in practice the computation is dominated by space complexity.
However, I haven't yet ported it over to a hashtable version, so not
sure.
(And the shootout example doesn't satisfy my sense of "dead simple.")
2009/7/18 Bulat Ziganshin <bulat.ziganshin at gmail.com>:
> Hello Thomas,
>
> Saturday, July 18, 2009, 2:24:21 AM, you wrote:
>
>> Further, is there a hashtable implementation for haskell that doesn't
>> live in IO? Maybe in ST or something?
>
> 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 implement a 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,(a,b))) list)
> )
>
> where arrsize = head$ filter (>size)$ iterate (\x->3*x+1) 1
> hashfunc a = hash a `mod` arrsize
>
>
> lookup a (HT hash arr) = List.lookup a (arr!hash a)
>
>
> main = do let assoclist = [("one", 1), ("two", 2), ("three", 3)]
> hash = create 10 (fromEnum . Data.HashTable.hashString) assoclist
> print (lookup "one" hash)
> print (lookup "zero" hash)
>
>
> --
> Best regards,
> Bulat mailto:Bulat.Ziganshin at gmail.com
>
>
More information about the Haskell-Cafe
mailing list