It seems like updates could be very fast because I assume // is implemented with a fast memcpy....
(//) is very slow
_________________________________________________________________ S. Alexander Jacobson mailto:me@alexjacobson.com tel:917-770-6565 http://alexjacobson.com
On Tue, 24 Feb 2004, JP Bernardy wrote:
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 Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
_______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
-- Hal Daume III | hdaume@isi.edu "Arrest this man, he talks in maths." | www.isi.edu/~hdaume