> It seems like updates could be very fast because I > assume // is implemented with a fast memcpy....
(//) is very slow > _________________________________________________________________ > S. Alexander Jacobson mailto:[EMAIL PROTECTED] > 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 > > [EMAIL PROTECTED] > > http://www.haskell.org/mailman/listinfo/haskell > > > > _______________________________________________ > Haskell mailing list > [EMAIL PROTECTED] > http://www.haskell.org/mailman/listinfo/haskell > -- Hal Daume III | [EMAIL PROTECTED] "Arrest this man, he talks in maths." | www.isi.edu/~hdaume _______________________________________________ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell