[Haskell] performance tuning Data.FiniteMap

JP Bernardy jyp_7 at yahoo.com
Tue Feb 24 14:44:46 EST 2004

> 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

Just my 2 cents,


Do you Yahoo!?
Yahoo! Mail SpamGuard - Read only the mail you want.

More information about the Haskell mailing list