Path: csiph.com!x330-a1.tempe.blueboxinc.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!border3.nntp.dca.giganews.com!Xl.tags.giganews.com!border1.nntp.dca.giganews.com!nntp.giganews.com!local2.nntp.dca.giganews.com!nntp.earthlink.com!news.earthlink.com.POSTED!not-for-mail NNTP-Posting-Date: Thu, 30 Jun 2011 14:02:42 -0500 Message-ID: <4E0CC851.470F@mindspring.com> Date: Thu, 30 Jun 2011 15:02:41 -0400 From: pete Reply-To: pfiland@mindspring.com Organization: PF X-Mailer: Mozilla 3.04Gold (WinNT; I) MIME-Version: 1.0 Newsgroups: comp.lang.c Subject: Re: offset 1 list indexing References: <87wrgc8k05.fsf@bazspaz.fatphil.org> <4E06168B.72B2@mindspring.com> <4e062307.139157618@text.giganews.com> <4e06aaa8.173880305@text.giganews.com> <4E06C8E2.F3D@mindspring.com> <87d3hx95j9.fsf@bazspaz.fatphil.org> <4E0A9DAB.2DB3@mindspring.com> <4e0b3475.471317521@text.giganews.com> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Lines: 320 X-Usenet-Provider: http://www.giganews.com NNTP-Posting-Host: 4.154.223.54 X-Trace: sv3-7ZMKyk+d0yUX1yatYX4baVgBEEswZy+7fDMrmxnfopp7InQTnPz7mMhxTxkt9CK6hM2vfZs4ZeTHtN+!DZ/FDf8ZmKE964nTDp84C2ebf0ifuHVhrnC9UEixasFjSsX6KtDwyCjiRWzTpwhmf8yJ1pbaYe/R!8Am5qhbP0w== X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly X-Postfilter: 1.3.40 X-Original-Bytes: 10917 Xref: x330-a1.tempe.blueboxinc.net comp.lang.c:7318 Richard Harter wrote: > > On Tue, 28 Jun 2011 23:36:11 -0400, pete > wrote: > > >Phil Carmody wrote: > >> > >> pete writes: > >> > Richard Harter wrote: > >> > > >> > > As far as heaps are concerned, > >> > > if you are doing the heap in an array thing, > >> > > you have two options > >> > > (more if you come up with some alternatives) > >> > > - you can have (slightly) more cumbersome code or you > >> > > can throw away a location. > >> > > >> > If you're writing a heapsort, > >> > one alternative is to use what I call a "casual heap" > >> > where the first element is its own first child. > >> > >> That's a curious approach, not one I've seen before. > > It turns out that it is an example of a standard approach that is > disguised by the notation. > > >> > >> > Then, the children of node n are at 2*n and 2*n+1. > >> > > >> > On the implementation that I'm using right now, > >> > I get faster times using the casual heap > >> > on sorting randomised arrays of long unsigned, > >> > even though the casual heap uses > >> > both more data comparisons and more data movement. > >> > I think the speed difference us cache related. > >> > > >> > http://www.mindspring.com/~pfilandr/C/e_driver/ > >> > >> MOV(&temp, array + parent); > >> > >> I see lots of use of temp in your code. And other people complain > >> about [0] not being used in 1-based heaps, and therefore wasted. > >> Unsurprisingly, these two aspects can annihilate each other. > > > >Not really. > >The 1 based array, is a larger array > >than a 0 based array of the same number of elements. > >The array which is being sorted, > >should persist beyond the lifetime of the objects > >which were declared in the sorting function. > > Actually you are using a disguised 1 based array that is a sub array > of the larger array. The structure looks like this: > > location 0: Largest element in the entire array > locations 1 to n-1: A heap containing n-1 elements with the heap head > at array[1]. The heap head is the second larget element in the entire > array. > > The logic in the "casual heap" code can be simplified a bit if you > keep the actual structure in mind, i.e., > > (1) Save array[0] in temp. > (2) Copy array[1] into array[0] > (3) Copy the current last into array[1] > (4) Copy temp into the current last loc > (5) Do a standard 1 based sift starting at array[1] > > Another way to skin this particular cat is to first find the minimum > element and swap it into location 0, then go ahead and do a standard > 1-based heapsort starting at location 1. Without testing I don't know > whether this is faster or slower. I've rewritten the example so that the functions work by byte swapping array elements with other array elements. In this example, the element type is "array of six char". The only object types that exist within the sorting functions are: 1 pointer to array of six char 2 pointer to unsigned char 3 unsigned char 4 size_t At no time is there any copy of any element being stored anywhere except in the 0 based array itself. /* BEGIN output from array_sort.c */ Arrays of element type (char [sizeof "seven"]), are being sorted by string length. This is the original order of the test array: zero one two three four five six seven eight nine Original order sorted by shpSort2p1, which is a 0 based ordinary heapsort: two six one five four nine zero eight seven three Original order sorted by shpSort2, which is a 0 based casual heapsort: two six one zero five nine four seven three eight /* END output from array_sort.c */ /* BEGIN array_sort.c */ #include #include #define E_TYPE char e_type[sizeof "seven"] #define GT(A, B) (strlen(*(A)) > strlen(*(B))) #define NUMBERS \ {"zero"},{"one"},{"two"},{"three"},{"four"}, \ {"five"},{"six"},{"seven"},{"eight"},{"nine"} #define SORT_FUNCTIONS \ {no_sort, "This is the original order of the test array:"}, \ {shpSort2p1,"Original order sorted by shpSort2p1,\n" \ "which is a 0 based ordinary heapsort:"}, \ {shpSort2, "Original order sorted by shpSort2,\n" \ "which is a 0 based casual heapsort:"} #define NMEMB(A) (sizeof (A) / sizeof *(A)) typedef E_TYPE; void no_sort (e_type *array, size_t nmemb); void shpSort2p1(e_type *array, size_t nmemb); void shpSort2 (e_type *array, size_t nmemb); int main(void) { size_t sort, element; const e_type numbers[] = {NUMBERS}; e_type array[NMEMB(numbers)]; struct sf { void (*function)(e_type *, size_t); const char *description; } sort_function[] = {SORT_FUNCTIONS}; puts("/* BEGIN output from array_sort.c */\n"); puts("Arrays of element type (char [sizeof \"seven\"]),"); puts("are being sorted by string length.\n"); for (sort = 0; sort != NMEMB(sort_function); ++sort) { memcpy(array, numbers, sizeof array); sort_function[sort].function(array, NMEMB(array)); puts(sort_function[sort].description); for (element = 0; element != NMEMB(array); ++element) { puts(array[element]); } putchar('\n'); } puts("/* END output from array_sort.c */"); return 0; } void no_sort(e_type *array, size_t nmemb) { array, nmemb; } static void ssiftDown2p1(e_type *array, size_t parent, size_t stop) { size_t child; unsigned char *p1, *p2, *end, swap; child = parent * 2 + 1; while (stop - parent > parent + 1) { if (GT(array + child + 1, array + child)) { ++child; } if (GT(array + child, array + parent)) { p1 = (unsigned char *)array + parent * sizeof *array; p2 = (unsigned char *)array + child * sizeof *array; end = p2 + sizeof *array; do { swap = *p1; *p1++ = *p2; *p2++ = swap; } while (p2 != end); parent = child; child = child * 2 + 1; } else { break; } } if (stop == child && GT(array + child, array + parent)) { p1 = (unsigned char *)array + parent * sizeof *array; p2 = (unsigned char *)array + child * sizeof *array; end = p2 + sizeof *array; do { swap = *p1; *p1++ = *p2; *p2++ = swap; } while (p2 != end); } } void shpSort2p1(e_type *array, size_t nmemb) { size_t i; unsigned char *p1, *p2, *end, swap; if (nmemb > 1) { i = nmemb-- / 2; while (--i != 0) { ssiftDown2p1(array, i, nmemb); } do { ssiftDown2p1(array, 0, nmemb); p1 = (unsigned char *)array; p2 = (unsigned char *)array + nmemb * sizeof *array; end = p2 + sizeof *array; do { swap = *p1; *p1++ = *p2; *p2++ = swap; } while (p2 != end); } while (--nmemb != 0); } } static void ssiftDown2(e_type *array, size_t parent, size_t stop) { size_t child; unsigned char *p1, *p2, *end, swap; child = parent * 2; while (stop - parent > parent) { if (GT(array + child + 1, array + child)) { ++child; } if (GT(array + child, array + parent)) { p1 = (unsigned char *)array + parent * sizeof *array; p2 = (unsigned char *)array + child * sizeof *array; end = p2 + sizeof *array; do { swap = *p1; *p1++ = *p2; *p2++ = swap; } while (p2 != end); parent = child; child = child * 2; } else { break; } } if (stop == child && GT(array + child, array + parent)) { p1 = (unsigned char *)array + parent * sizeof *array; p2 = (unsigned char *)array + child * sizeof *array; end = p2 + sizeof *array; do { swap = *p1; *p1++ = *p2; *p2++ = swap; } while (p2 != end); } } void shpSort2(e_type *array, size_t nmemb) { size_t i; unsigned char *p1, *p2, *end, swap; if (nmemb > 1) { i = --nmemb / 2 + 1; while (--i != 0) { ssiftDown2(array, i, nmemb); } do { ssiftDown2(array, 0, nmemb); p1 = (unsigned char *)array; p2 = (unsigned char *)array + nmemb * sizeof *array; end = p2 + sizeof *array; do { swap = *p1; *p1++ = *p2; *p2++ = swap; } while (p2 != end); } while (--nmemb != 0); } } /* END array_sort.c */ -- pete