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

[T. William Wells]

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.

Right. And remember that for buildings of any size, the stuff
built on the foundation requires more time and effort to build
than the foundation does. This is not intended as a defence of
the false notion that efficiency is more important than a good
algorithm, but rather to show that the analogy is not relevant.

> 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.

Ok, what is a bad algorithm?

	A bubble sort?

	Well, I've used one where I had a small number of items
	to sort, no memory to spare, and irrelevant execution
	time constraints.

	A selection sort?

	I've used this where the number of items was not too
	large and the cost of moving an item was huge.

	An insertion sort?

	I've used this one where the insertion time was
	irrelevant but the cost of memory and code was important.

	A Shell sort?

	I use this sort if the number of items is reasonable and
	the code complexity or memory requirements of an O(n*ln
	n) sort is prohibitive.

	A quicksort?

	Actually my favorite non-memory-hog sort, I use this
	when I have no good reason to favor another sort.

	A heapsort?

	I use this one when I need to be able to use the sorted
	items as a queue.

	A linked-list sort?

	Once upon a time I got very tired of the slowness of the
	UNIX sort program. So I wrote a clone of it. I invented a
	whole new algorithm for it which you could call a
	linked-list merge sort.  It beat every other sort method
	that I tested hands-down.  Its only drawback is the
	memory for the linked list.  (Actually, I'd bet that
	someone invented this sort before me, but at the time,
	I'd never heard of anything like it.)

	A radix sort?

	I just finished coding one of these for a program which
	burns incredible amounts of time on our Sun. It just so
	happens that one critical piece of code sorts items by
	length and the maximum length is easy to compute and
	always small.

	[A sort algorithm with no name.]

	I invented a new hashing scheme; someone else here
	discovered a way to use it as a sorting method. How about
	a constant time sort that uses a fair amount of memory?
	It is often just the right tool for in-memory sorting of
	small keys.

In each case, the algorithm selected was the right one for the
job. None of these, not even the bubble sort, is a *bad*
algorithm; at worst, one could call them inappropriate.

Now that I have displayed my credentials :-), let me elaborate
on my previous posting. Writing a program has many steps.  Among
them are choosing an algorithm and coding the algorithm. Failure
to do either results in the non-existence of the program. Doing
either badly results in a poorer program than could have been.

It is not legitimate to say that choosing a better algorithm is
more important than implementing it efficiently.  Nor the
reverse.  To emphasize this: a programmer who can only select
among algorithms (assuming this to be possible, actually, it
isn't) is as poor a programmer as one who who can only code
efficiently.  And the best programmers have a large toolbox of
algorithms and a large selection of good coding techniques.

Most people who defend the notion that there are good and bad
algorithms try to treat algorithms as if they exist in a vacuum.
This is Idealist hokum. Algorithms exist to serve purposes, the
quality of a given algorithm is simply how well it serves a
given purpose and thus can not be spoken of independently of
said purpose.