[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:me@alexjacobson.com 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 Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell