[Haskell] performance tuning Data.FiniteMap

[JP Bernardy]

> 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