[Haskell] performance tuning Data.FiniteMap

[Hal Daume III]

> 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 at 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 at haskell.org
> > http://www.haskell.org/mailman/listinfo/haskell
> >
> 
> _______________________________________________
> Haskell mailing list
> Haskell at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell
> 

-- 
 Hal Daume III                                   | hdaume at isi.edu
 "Arrest this man, he talks in maths."           | www.isi.edu/~hdaume