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