Performance horrors

[John Meacham]

On Wed, Aug 27, 2008 at 04:48:41PM +0100, David House wrote:
> 2008/8/27 Adrian Hey <ahey at iee.org>:
> > As does the O(n*(log n)) AVL based nub I just wrote.
> 
> Care to share?
> 
> WDYT about using RULES to rewrite to nubOrd if an Ord context is
> available, as John Meacham mentioned?
> 
> John: you said you were uneasy about changing the complexity of an
> algorithm using RULES, but this is exactly what list fusion does
> (albeit for space, not time).

Indeed. and I am a little uneasy about that too :) not that I don't
think it is an excellent idea and reap the benefits of fast list
operations.. O(n^2) to O(n log n) just feels like a bigger jump to me
for some reason. I think in the end, the RULES are a good idea, but I
personally try to make which one I am using explicit when possible.
Hence making my ideas as to the time/space requirements for an operation
to both the compiler and a future reader of the code.

        John


-- 
John Meacham - ⑆repetae.net⑆john⑈