Re: Hoare's gripes about Ada (should be so what)

Re: Hoare's gripes about Ada (should be so what)

[Colin James 0621]

  
Ted Holden writes about what Tony Hoare says about Ada.  But Hoare is
not really qualified to have anything but an opinion, being a math
lecturer and not a software engineer (or that dirty word projammer).
  
When in seminary in the UK about ten years ago, I wrote Hoare regarding
an improvement in the pointer performance of his quicksort.  He did not
respond (no $'s ?), unusual for an Oxford don.  
  
But for those interested, I now have an optimized distribution counting
sort (unfortunately I was paid to write it in C since our C compiler did
not come with one).  It works in the same manner as sorting a deck of 
playing cards into suits first.  It is faster than quicksort for all
worst cases and is also stable (equal keys remain in the original order).
I'll share it with those interested since the taxpayer paid for it.
 
Since quicksort was made famous by Hoare (or vice versa), I wonder why
it is so universally used (especially in the C community) when Donald
Knuth's big 0 statistics clearly show distribution counting is faster.

Re: Hoare's gripes about Ada (should be so what)

[Michael Feldman]

In article <9308252104.aa09026@dsc.blm.gov> cjames@DSC.BLM.GOV (Colin James 062
1) writes:
>
>  
>Ted Holden writes about what Tony Hoare says about Ada.  But Hoare is
>not really qualified to have anything but an opinion, being a math
>lecturer and not a software engineer (or that dirty word projammer).
>  
>When in seminary in the UK about ten years ago, I wrote Hoare regarding
>an improvement in the pointer performance of his quicksort.  He did not
>respond (no $'s ?), unusual for an Oxford don.  

People like Ted are the kind who are always dumping on professors but
have mo hesitation about quoting them selectively.
>  
>But for those interested, I now have an optimized distribution counting
>sort (unfortunately I was paid to write it in C since our C compiler did
>not come with one).  It works in the same manner as sorting a deck of 
>playing cards into suits first.  It is faster than quicksort for all
>worst cases and is also stable (equal keys remain in the original order).
>I'll share it with those interested since the taxpayer paid for it.
> 
I'll take a copy. An Ada version could turn up in an insanely great
data structures book. You'll get full credit, of course.

>Since quicksort was made famous by Hoare (or vice versa), I wonder why
>it is so universally used (especially in the C community) when Donald
>Knuth's big 0 statistics clearly show distribution counting is faster.
>
Hey Ted, what's big O?

Mike Feldman

Re: Hoare's gripes about Ada (should be so what)

[Ste ve Masticola]

mfeldman@seas.gwu.edu (Michael Feldman) writes:

>>Since quicksort was made famous by Hoare (or vice versa), I wonder why
>>it is so universally used (especially in the C community) when Donald
>>Knuth's big 0 statistics clearly show distribution counting is faster.
>>
>Hey Ted, what's big O?

>Mike Feldman

Asymptotic upper bound for growth in complexity, sometimes read as
"order". E.g.: "Heapsort requires O(n log n) comparisons worst case,
where n is the number of items to be sorted." I'm sure you've seen it
before.

Little o, on the other hand, is an asymptotic lower bound, as in,
"Sorting has been proven to require at least o(n log n) comparisons in
the worst case." (BTW, this holds for hashing sorts, too, if you look
at it closely.)

And, to tell you the truth, I don't know what the heck distribution
counting is... :-) Anyone care to enlighten me?

Pedantically yours,
- Steve (masticol@scr.siemens.com).

Re: Hoare's gripes about Ada (should be so what)

[agate!howland.reston.ans.net!darwin.sura.net!jabba.ess.harris.com!dr3w!sm]

In article <1993Sep1.030349.9524@seas.gwu.edu>, mfeldman@seas.gwu.edu
(Michael Feldman) writes:
|> I'll take a copy. An Ada version could turn up in an insanely great
|> data structures book. You'll get full credit, of course.
|> 

Heck, if you're taking contributions, why not include the SlowSort?
It has to be just about the *worst* sorting algorithm ever devised!
I use it as a orientation exercise in my Ada training courses.  Kinda
fun to watch a 14 element sort take 10 minutes to finish!  :-)

-- 
Scott McCoy     Harris Corp. Information Systems Division
Staff Eng-SW    Opinions expressed are my own.

Re: Hoare's gripes about Ada (should be so what)

[Mark A Biggar]

In article <CCoI96.DqH@jabba.ess.harris.com> smccoy@dr3w.ess.harris.com (Scott 
McCoy) writes:
>In article <1993Sep1.030349.9524@seas.gwu.edu>, mfeldman@seas.gwu.edu
>(Michael Feldman) writes:
>|> I'll take a copy. An Ada version could turn up in an insanely great
>|> data structures book. You'll get full credit, of course.
>Heck, if you're taking contributions, why not include the SlowSort?
>It has to be just about the *worst* sorting algorithm ever devised!
>I use it as a orientation exercise in my Ada training courses.  Kinda
>fun to watch a 14 element sort take 10 minutes to finish!  :-)

I don't know what the algorithm for Slowsort is but the two worst sorting 
algorithms I know of are permutation-sort and 52-pickup-sort.

Permutation-sort sometimes shows up in prolog programs by a naive 
translation of the declaritive definition of sorting directly into prolog:

sort(List) :- permute(List),ordered(List).

I.E. using a backtracking algorithm to produce succesive permutations of the
original list and then checking if the new permutation is ordered.

Even worse is 52-pickup sort, which is also easy to express in prolog:

sort(List) :- random-shuffle(list),order(list).

I.E. this is like sorting a deck of cards by throwing it up in the air,
picking up all the cards (without looking at them) and then checking if
they just happen to be sorted, if not repeat.  You can't even express an 
big O bound for this alogorithm, only an expected number of iterations.

--
Mark Biggar
mab@wdl.loral.com

Re: Hoare's gripes about Ada (should be so what)

[Peter Juhl]

I apologize if this appears twice in different forms, I posted
a preliminary version. Doug McIlroy had numerous suggestions
for improvements, I hereby send a more readable article (the first
one should have been canceled, but one never knows.) 

I think that it has some interest.

Colin James's remarks about quicksort vs distribution sort (hereafter
called radix sort) must be tempered according to circumstances.  It is
not clear exactly which big-O estimates he referred to, but it is
worth warning that the occasionally made claim that quicksort takes
time N log N while radix sort only takes time N makes sense only if
you give entirely different interpretations to N in the two cases.

If you have N records comprising a total volume of V "digits" of data,
then performance scales like

        quicksort, expected:  N log N comparisons
        quicksort, worst:  N^2 comparisons
        big-end radix, expected:  N log N digit inspections
        big-end radix, worst:  V digit inspections
        little-end radix, always:  V digit inspections

V is usually bigger - often much bigger - than N log N.

If you are comparing strings, comparisons take expected time at least
log N, not time 1.  Thus for strings quicksort has expected time N
log^2 N. The worst case is VN.

So it all depends on what you are sorting.  If keys can be represented
as strings, and keys must be compared as strings, then big-end radix
sort is a good thing.

If it should happen that V is not much bigger than N log N and keys
are essentially strings, then little-end radix is a good thing.

Radix sorting has considerable bookkeeping overhead.  Under the
conditions set forth above, it is definitely a win, but not without
substantial programming effort.  So quicksort is not dead:  it is easy
to get right with reasonable efficiency, and it is the only game in
town when keys cannot be compared as strings.

A little-known hybrid of radix sort and quicksort gets around the
problem of string comparison taking expected time log N, at the cost
of a larger scaling constant, without the bookkeeping hassle of radix
sorting.  Partition on first digits into three parts
(less,equal,greater).  In the less and greater parts partition
recursively on first digits.  In the equal part partition sort
recursively on second digits and so on.

Both research Unix and BSD Unix currently use radix sort in their sort
utilities.

All this and more can be found in the article, "Engineering radix
sort", by McIlroy, Bostic, and McIlroy in "Computing Systems" 6 (1993)
5-27.  Another recent article is Davis, "A fast radix sort", in
"Computer Journal" 35 (1992) 636-642.  Both articles contain effective
programs written in C. For a fast C qsort, based on quicksort, see
Bentley and D McIlroy to appear next November in "Software Practice
and Experience".  For the speed-champion qsort (which isn't based on
quicksort) see P McIlroy in the proceedings of the Symposium on
Discrete Algorithms, Austin, 1993.

Incidentally, Hoare is an excellent software engineer.

--- peter (peju@research.att.com)

Re: Hoare's gripes about Ada (should be so what)

[Robert Dewar]

Boy this is getting off the topic, but it's hard to stand by quietly and
see blatantly incorrect technical comments.

"Sorting has been proved to take O(n log n) time"

is plain wrong. This bound applies only if the sorting is restricted to
comparisons. If arithmetic operations are required, this bound obviously
does not apply. Consider a trivial case of sorting a huge pile of numbers
in the range 1 .. 100.

This has an obvious O(N) implementation (just keep an array of 100 entries
which count the number of occurrences of each possible entry). By using
linked lists, other associated data can be carried along, still in O(N)
time.

Address distribution sorting has an expected average performance much
better than O (N long N), in fact it approaches linear performance
asymptotically in the average case if your distribution function is
well behaved. A lot of large scale sorting (the kind done on giant mainframes
with zillions of records) uses address calculation sorting.

Finally, note that in this day of parallel machines, even if you are
restricted to comparisons, you can do much better than O (N log n).

Re: Hoare's gripes about Ada (should be so what)

[Robert Dewar]

How about a small sort contest. Suppose you want to write an Ada sort with
the spec:

	type x is array (integer range <>) of integer;
	procedure sort (data : in out x); -- sorts into ascending order

What's the least number of Ada tokens (counting from the IS to the semicolon
following the END) that implements this spec?

Re: Hoare's gripes about Ada (should be so what)

[Michael Feldman]

In article <CCoI96.DqH@jabba.ess.harris.com> smccoy@dr3w.ess.harris.com (Scott 
McCoy) writes:
>
>In article <1993Sep1.030349.9524@seas.gwu.edu>, mfeldman@seas.gwu.edu
>(Michael Feldman) writes:
>|> I'll take a copy. An Ada version could turn up in an insanely great
>|> data structures book. You'll get full credit, of course.
>|> 
>
>Heck, if you're taking contributions, why not include the SlowSort?
>It has to be just about the *worst* sorting algorithm ever devised!
>I use it as a orientation exercise in my Ada training courses.  Kinda
>fun to watch a 14 element sort take 10 minutes to finish!  :-)
>
Sure - send a copy this way. I'm not sure which one you mean, but figure
it'll be pretty close to the one my students always re-invent :-)

Mike Feldman

Re: Hoare's gripes about Ada (should be so what)

[Wes Groleau x1240 C73-8]

I already dropped the post, so I don't know who the guilty party is, but:

When a certain demagogue misquotes, or exaggerates the words of a respected
member of our profession, one of two responses (IMHO) is appropriate:

1. Ignore him.
2. Flame the demagogue.

IMHO, flaming the "respected member" is not appropriate even if the "respected
member" is wrong.

Those who are aware that demagogue is not the right word, please correct me
without flames.

Re: Hoare's gripes about Ada (should be so what)

[Dag Bruck]

In <comp.lang.ada> dewar@cs.nyu.edu (Robert Dewar) writes:
>How about a small sort contest. Suppose you want to write an Ada sort with
>the spec:
>
>	type x is array (integer range <>) of integer;
>	procedure sort (data : in out x); -- sorts into ascending order
>
>What's the least number of Ada tokens (counting from the IS to the semicolon
>following the END) that implements this spec?

Here's my contribution (appologies for any syntax errors):

	..... IS
	   NULL;
	END;

The implementation is not very correct, but what the heck.

			-- Dag B, C++ programmer :-)

Re: Hoare's gripes about Ada (should be so what)

[Robert Dewar]

Mr. Bruck, I am afraid that perhaps you have not quite got the spirit of
Ada yet. Whereas in some other languages, particularly those with a one
letter name, there may be a tradition that brevity is more important than
correctness, I have to report to you that in the Ada world, we are quite
interested in correct reliable programs. I realize that this consigns Ada
to a small niche, the niche of reliable software, but that's the way it is!

Consequently, I am afraid that the judges will have to reject your 
submission in the "shortest search contest". 

Better luck next time

:-) :-) :-) :-) :-) :-)
(big row of smiley's just in case someone takes this seriously! :-)

Re: Hoare's gripes about Ada (should be so what)

[Michael Feldman]

In article <263mb7$mpd@schonberg.cs.nyu.edu> dewar@cs.nyu.edu (Robert Dewar) wr
ites:

[deletia]
>
>Finally, note that in this day of parallel machines, even if you are
>restricted to comparisons, you can do much better than O (N log n).
>
...but not in Ada :-)

How's that for getting back on the subject?

Mike

Re: Hoare's gripes about Ada (should be so what)

[Dag Bruck]

In <comp.lang.ada> dewar@cs.nyu.edu (Robert Dewar) writes:
>.... I have to report to you that in the Ada world, we are quite
>interested in correct reliable programs.
>
>Consequently, I am afraid that the judges will have to reject your 
>submission in the "shortest search contest". 

Dear Sirs,

I kindly ask you to reconsider my submission with the following
motivation.

I claim that my program is intuitively and _provably_ correct for a
semi-infinite number of inputs, i.e., those already sorted.  I also
hope that the structure of my program lends itself to automated
correctness proving.  This is a in my view a great asset over many
other algorithms that are very hard, or impossible, to _prove_
correct.

You should also take into consideration the significant practical
advantages of the code:

	- easy to understand
	- fits on one page
	- easy to maintain
	- runtime efficient

Sorting routine follows:

	.... IS
	    NULL;
	END;

Best regards,


Dag M. Bruck
C++ programmer, LSD is no fun

Re: Hoare's gripes about Ada (should be so what)

[Wes Groleau x1240 C73-8]

In article <26qfqe$p4m@nic.lth.se> dag@control.lth.se (Dag Bruck) writes:
>In <comp.lang.ada> dewar@cs.nyu.edu (Robert Dewar) writes:
>>.... I have to report to you that in the Ada world, we are quite
>>interested in correct reliable programs.
>
>Dear Sirs,
>I kindly ask you to reconsider my submission with the following

Dear Sirs:
I kindly ask you to reconsider your subject line with each submission.
Here in the comp.lang.ada world, we are quite interested in seeing something
about Hoare's gripes when the subject line promises it.

Wes G.
:-) :-) :-)