Christopher Lane Hinson
lane at downstairspeople.org
Wed Aug 27 21:38:18 EDT 2008
On Wed, 27 Aug 2008, Adrian Hey wrote:
>> Using RULES in this way could be a pessimization. I can't imagine a nubOrd
>> that would ever be as performant as nub on very small data sets (two or
>> three elements).
> Why not? comparison doesn't cost any more than equality testing and I
> think we can safely say that nubOrd will never require *more*
> comparisons than equality tests needed by nub.
I think that you will have to do extra comparsons to build whatever
ordered data structure you use, and extra work to keep it balanced or you
will risk falling back on O(n^2) behavior, and feed the garbage collector
a little bit more with discarded intermediate nodes.
Whether this is a real problem or not is for empirical testing assuming
anyone cares that much.
I actually really like the RULES idea. There seemed to be an intuition
that changing the complexity of a function using RULES is a bad idea,
and I was putting forward a possible basis for that intution.
A rule of thumb is that when you switch to an algorithm with a better
complexity class, you pay at least a small price in the constant factor.
More information about the Libraries