[gclist] Name that hypothesis

[Charles Fiterman]

>Hmmm... I think it's a bit dangerous to say that continuous random
>process are an acceptable model of an unknown set of unknown anythings.
>(I'm not sure we disagree, but I think the vocabulary can be misleading.)
>If something's unknown, you can't model it with any real confidence,
>and using "continuous random processes" is likely to introduce huge
>biases.  Program behavior is often discontinuous and almost always
>nonrandom (i.e., it's usually phased and strongly patterned).

I've had a fair amount of experience optomizing sorts and the qsort
I wrote for Mark Williams won all the benchmarks and by very wide
margins. I think my experience is important here.

The trick was to avoid disaterous behavior in special cases not to
optomize every nanosecond out of normal cases. You want to think about
the worst thing that can ever happen because there will be programs
that do exactly that. In the case of qsort the worst thing that can
ever happen is choosing a succession pivots that put everything on one 
side. Since a lot of qsorts use center pivot that means the merging
deck case [1 ... 100000 1 ... 100000] is the disaster. Detecting
bad pivots and adjusting caused me to run this benchmark in three
seconds while others were taking twelve hours. What I did was to
start with a center pivot and if the results were bad go 1/4 in for
the next try then 1/8 then switch to shellsort which is best for many 
duplicate keys.

So the question of all these algorithms is "Can you design a disasterous
case? And what can you do to get reasonable performance anyway?" If
you can do reasonably for a succession of programs you will win the
benchmarks. Instead of asking about normal program behavior as if
there was such a thing can you write a program that really screws
things up.

Charles Fiterman	Geodesic Systems
Phone 312-728-7196	4745 N. Ravenswood Suite 111
Fax   312-728-6096	Chicago Il 60015
cef@geodesic.com

A computer language without garbage collection
  is like a city without garbage collection.