Re: Peter Chen and Charles Bachman

From: Brian Inglis <Brian.Inglis_at_SystematicSw.Invalid>
Date: Mon, 14 Jun 2004 14:29:36 GMT
Message-ID: <trcrc0dou9hpp9i6mpvv8pv6tb0j8sipfo_at_4ax.com>


On Mon, 07 Jun 2004 11:01:17 -0700 in comp.databases.theory, Gene Wirchenko <genew_at_mail.ocis.net> wrote:

>Brian Inglis <Brian.Inglis_at_SystematicSw.Invalid> wrote:
>
>>On Tue, 25 May 2004 19:01:45 -0700 in comp.databases.theory, Gene
>>Wirchenko <genew_at_mail.ocis.net> wrote:
>>
>>>Leandro Guimaraens Faria Corsetti Dutra <leandro_at_dutra.fastmail.fm>
>>>wrote:
>>>
>>>>Em Thu, 20 May 2004 16:00:37 -0700, Gene Wirchenko escreveu:
>>>>
>>>>> Leandro Guimaraens Faria Corsetti Dutra <leandro_at_dutra.fastmail.fm>
>>>>> wrote:
>>>>>
>>>>>>Em Wed, 19 May 2004 23:22:34 -0700, Gene Wirchenko escreveu:
>>>>>>
>>>>>>> I see no advantage to
>>>>>>> being stuck with having to do something one way only.
>>>>>>
>>>>>> Have you ever grokked _GOTO considered harmful_, or Codd's
>>>>>>rules?
>>>>>
>>>>> The former most definitely; the latter, not yet. There are times
>>>>> when a well-placed goto will aid program clarity.
>>>>
>>>> Only if the language is poor.
>>>
>>> You are too doctrinaire for me.
>>>
>>> One of the fast sorts has a structure whose symmetry wrt to two
>>>variables is obvious with a couple of gotos, but which is lost with
>>>structured code.
>>
>>Are you perhaps referring to the quicksort partitioning step?
>>If solution symmetry is lost in "structured" code, blame the
>>programmer's poorly structured thinking, and not the poorly structured
>>code.
>
> When the code is structured the symmetry is not in the code. The
>two variables appear quite different in use. Do you have a version
>that retains the symmetry IN THE CODE?

The only asymmetry below seems to be the optimization that requires a specific order of operations to replace element swaps by moves. Opinion?

[setup code elided]
/* get median value and empty left slot */

    move( temp, median, no_bytes);
    move( median, left, no_bytes);
/* while partitions do not meet */

    while (left < right)
    {

/* scan from right to left while values >= median	*/
	while (left < right && compare( item_cmp, right, temp) >= 0)
	    right -= gap;
/* if not partitioned, move out of order value to left	*/
	if (left < right)
	{
	    move( left, right, no_bytes);
	    left += gap;
/* scan from left to right while values <= median	*/
	    while (left < right && compare( item_cmp, left, temp) <= 0)
		left += gap;
/* if not partitioned, move out of order value to right */
	    if (left < right)
	    {
		move( right, left, no_bytes);
		right -= gap;
	    }
	} /* if not partitioned */
    } /* while not partitioned	*/
/* replace saved item in empty slot	*/

    move( left, temp, no_bytes);
    print_sort_trace( list, no_items, no_bytes); /* sort smaller partition first in case bad median chosen */

    lsize = left - list;
    litems = lsize/no_bytes;
    left -= gap;
    right += gap;
    rsize = end_list - right;
    ritems = rsize/no_bytes;
    if (++depth > max_nest_depth)

        max_nest_depth = depth;
/* sort left partition first if smaller */

    if (lsize < rsize)
    {

	if (litems > skip_threshold)
	    quick_sort( list, litems, no_bytes, item_cmp);
	else
	if (litems > 1)
	    (*skip_sort)( list, litems, no_bytes, item_cmp);
	if (ritems > skip_threshold)
	    quick_sort( right, ritems, no_bytes, item_cmp);
	else
	if (ritems > 1)
	    (*skip_sort)( right, ritems, no_bytes, item_cmp);
    }
    else	/* right partition smaller so sort first	*/
    {
	if (ritems > skip_threshold)
	    quick_sort( right, ritems, no_bytes, item_cmp);
	else
	if (ritems > 1)
	    (*skip_sort)( right, ritems, no_bytes, item_cmp);
	if (litems > skip_threshold)
	    quick_sort( list, litems, no_bytes, item_cmp);
	else
	if (litems > 1)
	    (*skip_sort)( list, litems, no_bytes, item_cmp);
    }
-- 
Thanks. Take care, Brian Inglis 	Calgary, Alberta, Canada

Brian.Inglis_at_CSi.com 	(Brian dot Inglis at SystematicSw dot ab dot ca)
    fake address		use address above to reply
Received on Mon Jun 14 2004 - 16:29:36 CEST

Original text of this message