Value of microeffiency (was: Re: Optimal ...)

[Richard Harter]

In article <449 at proxftl.UUCP> bill at proxftl.UUCP (T. William Wells) writes:
>In article <3693 at rpp386.UUCP>, jfh at rpp386.UUCP (John F. Haugh II) writes:
>> In article <416 at proxftl.UUCP> bill at proxftl.UUCP (T. William Wells) writes:
>> >In article <3401 at rpp386.UUCP>, jfh at rpp386.UUCP (John F. Haugh II) writes:
>> >> i don't know what value microefficiency has this week, but in general,
>> >> writing good solid algorithms is what is important.

>> >        There is no argument against the idea that a good
>> >algorithm is the proper base from which to start (though there is
>> >certainly room for discussion as to what constitutes a good
>> >algorithm). But, a good algorithm is ONLY THE BEGINNING.

>> er, just the same way the in order to build a strong building you have
>> to have a solid foundation.  but that is, after all, only the beginning.
>> if i write a sort routine with O(n*ln n) and you write one O(n**2),
>> how much ``micro optimization'' is it going to take to outperform my
>> poorly implemented, but superior time complexity, algorithm?  if your
>> idea of a really swell sort algorithm is a bubble sort, no matter how
>> much optimizing you perform you are going to lose.

>> even a highly optimized bad algorithm is still a bad algorithm.

Wells discusses at length the point that 'good' and 'bad' are context
dependent terms when applied to algorithms, with particular reference
to sorting algorithms.

What he did not do is point out that John's comments were a nonresponsive
false dichotomoty.  The original comment ammounts to:

"Pick the right algorithm and then optimize it."

John's response amounts to:

"An optimized bad algorithm is worse than a good algorithm."

When it is stated this baldly it is fairly clear than John has simply
ignored the point being made and has posed a false dichotomy.  John's
comment is faulty on two grounds.

First, as Wells points out, "good" and "bad"  depend on context; an
O(f(n)) evaluation is inadequate.  Secondly, the original point is
important -- once one has chosen the "right" algorithm, it is still
important (and profitable) to implement it efficiently.  As we all
know, there are a host of tradeoffs to consider, such as maintainability,
cost of constructing an optimized version, the return from optimization,
and, of course, the cost of analyzing the tradeoffs.  

-- 

In the fields of Hell where the grass grows high
Are the graves of dreams allowed to die.
	Richard Harter, SMDS  Inc.