Performance horrors

[Christopher Lane Hinson]

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.

--Lane