> 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 [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
