Re: Performance horrors

On Wed, Aug 27, 2008 at 04:48:41PM +0100, David House wrote:

2008/8/27 Adrian Hey :

...

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⑈