[Rewrote prior code to be cleaner] Isn't the following more efficient than Data.FiniteMap?
class Ix a=>Radix a where maxRange::(a,a) class Radix a => HashKey b a where hashKey::b->[a] instance Radix Char where maxRange=(chr 0,chr 255) instance Radix a=> HashKey [a] a where hashKey x=x data HT radix elt = HT (Maybe (Array radix (HT radix elt))) (Maybe elt) emptyHT=HT Nothing Nothing emptyArray = Just (array maxRange [(x,emptyHT) | x<- [(fst maxRange)..(snd maxRange)]]) hLookup table key = hLookup' table (hashKey key) hLookup' (HT x y) [] = y hLookup' (HT Nothing _) _ = Nothing hLookup' (HT (Just ar) _) (k:ey) = hLookup' (ar!k) ey --insert table key val = insert' table (hashKey key) val insert' (HT x _) [] val = HT x val insert' (HT Nothing y) key val = insert' (HT emptyArray y) key val insert' (HT (Just ar) y) (k:ey) val = HT (Just $ ar//[(k,insert' (ar!k) ey val)]) y Isn't hLookup substantially faster than the binarySearch in FiniteMap for e.g. Strings? Doesn't insert compete with FiniteMap because small array copies should be blisteringly fast? Also, basic Haskell questions: * How do I get insert to typecheck? insert' works fine. * How do I hide the "lookup" automatically imported from GHC.List? -Alex- _________________________________________________________________ S. Alexander Jacobson mailto:[EMAIL PROTECTED] tel:917-770-6565 http://alexjacobson.com > On Tue, 24 Feb 2004, JP Bernardy wrote: > > > > > > I believe FiniteMap works by representing the data > > > in binary trees. It is therefore O(log2(n)) to > > > read and update. > > > > > > However, if my application reads many more times > > > than it writes, then perhaps I can get a > > > substantial performance boost by increasing the > > > branch factor on the tree. For example, if each > > > node was an array of 256 elements, reads would be > > > O(log256(n)), a 128x improvement! > > > > Not quite. > > > > In fact, O(log256(n)) is equivalent to O(log2(n)), > > because there is only a constant factor between the > > two. That's why basis of logarithms are usually > > omitted in O() expressions. > > > > Besides, the ratio between log256(n) and log2(n) is > > more like 8 than 128. (And you'd loose this factor > > in searching the right subtree, as Ketil pointed out) > > > > Tuning Data.FiniteMap probably is not what you want. > > > > I don't know, but you can have a look at > > Data.Hashtable. > > > > Just my 2 cents, > > JP. > > > > > > > > __________________________________ > > Do you Yahoo!? > > Yahoo! Mail SpamGuard - Read only the mail you want. > > http://antispam.yahoo.com/tools > > _______________________________________________ > > Haskell mailing list > > [EMAIL PROTECTED] > > http://www.haskell.org/mailman/listinfo/haskell > > > > _______________________________________________ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
