[Haskell] performance tuning Data.FiniteMap
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!
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