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: Sun, 26 Jun 2011 23:30:31 -0500 Message-ID: <4E080768.2E74@mindspring.com> Date: Mon, 27 Jun 2011 00:30:32 -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> <4e07522a.216764450@text.giganews.com> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Lines: 265 X-Usenet-Provider: http://www.giganews.com NNTP-Posting-Host: 4.154.217.214 X-Trace: sv3-T2ZkvMQ/cW9IuzZqPgRYNtBAwh4x73g10vAg+nmhm1FjcjxAZuwrfxlab+7IwtHteAbvbOKKGgBmngw!P99gud51CI48zpVXV/G4XFAo9Wvn0yEMgISxnwULiLsQtTzN0B+3jx9vBWxeMlv/LlUGzNrHwQMu!IRNGVzazpLk= 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: 8351 Xref: x330-a1.tempe.blueboxinc.net comp.lang.c:7015 Richard Harter wrote: > > On Sun, 26 Jun 2011 01:51:30 -0400, pete > wrote: > > >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. > >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. > > Interesting. When you say faster times what are you comparing your > casual heap against - 0-based indexing or 1-based indexing? 0 based. > I'm not > use I follow your "the first element is its own first child". Does > "first" refer only to the beginning of the heap or is it a generic > thing running down the heap. A simple example would be useful. "first" refers to the first element of the array being sorted. The 0 based casual heapsort function heapSort2(), uses the helper function siftDown2(). siftDown2() contains this statement: child = parent * 2; The 0 based ordinary heapsort function heapSort2p1(), uses the helper function siftDown2p1(). siftDown2p1() contains this statement: child = parent * 2 + 1; /* BEGIN output from ptr_sort.c */ An array of elements of type (char *) is 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 heapSort2, which is a 0 based casual heapsort: two six one zero five nine four seven three eight Original order sorted by heapSort2p1, which is a 0 based ordinary heapsort: two six one five four nine zero eight seven three /* END output from ptr_sort.c */ /* BEGIN ptr_sort.c */ /* ** lencomp() compares pointers to strings, ** according to string length. */ #include #include #include #define SORT_FUNCTIONS \ no_sort, "This is the original order of the test array:",\ heapSort2, "Original order sorted by heapSort2,\n" \ "which is a 0 based casual heapsort:", \ heapSort2p1,"Original order sorted by heapSort2p1,\n" \ "which is a 0 based ordinary heapsort:" #define NUMBERS \ "zero","one","two","three","four", \ "five","six","seven","eight","nine" #define E_TYPE char *e_type #define GT(A, B) (lencomp((A), (B)) > 0) #define MOV(A, B) ((void)(*(A) = *(B))) #define NMEMB(A) (sizeof (A) / sizeof *(A)) #define SWAP(A, B, T) (MOV(T, A), MOV(A, B), MOV(B, T)) typedef E_TYPE; int lencomp(const void *, const void *); void no_sort (e_type *array, size_t nmemb); void heapSort2 (e_type *array, size_t nmemb); void heapSort2p1(e_type *array, size_t nmemb); int main(void) { size_t element, sort; struct sf { void (*function)(e_type *, size_t); const char *description; } sort_function[] = {SORT_FUNCTIONS}; const e_type numbers[] = {NUMBERS}; e_type copy[NMEMB(numbers)]; puts("/* BEGIN output from ptr_sort.c */\n"); puts("An array of elements of type (char *)"); puts("is being sorted by string length.\n"); for (sort = 0; sort != NMEMB(sort_function); ++sort) { puts(sort_function[sort].description); memcpy(copy, numbers, sizeof copy); sort_function[sort].function(copy, NMEMB(numbers)); for (element = 0; element != NMEMB(numbers); ++element) { puts(copy[element]); } putchar('\n'); } puts("/* END output from ptr_sort.c */"); return 0; } int lencomp(const void *a, const void *b) { const size_t a_len = strlen(*(const e_type *)a); const size_t b_len = strlen(*(const e_type *)b); return b_len > a_len ? -1 : b_len != a_len; } void no_sort(e_type *array, size_t nmemb) { array, nmemb; } static void siftDown2(e_type *array, size_t parent, size_t end) { size_t child; e_type temp; MOV(&temp, array + parent); child = parent * 2; while (end - parent > parent) { if (GT(array + child + 1, array + child)) { ++child; } if (GT(array + child, &temp)) { MOV(array + parent, array + child); parent = child; child *= 2; } else { MOV(array + parent, &temp); return; } } if (end == child && GT(array + child, &temp)) { MOV(array + parent, array + child); parent = child; } MOV(array + parent, &temp); } void heapSort2(e_type *array, size_t nmemb) { size_t i; e_type temp; if (nmemb > 1) { i = --nmemb / 2 + 1; while (--i != 0) { siftDown2(array, i, nmemb); } do { siftDown2(array, 0, nmemb); SWAP(array, array + nmemb, &temp); } while (--nmemb != 0); } } static void siftDown2p1(e_type *array, size_t parent, size_t end) { size_t child; e_type temp; MOV(&temp, array + parent); child = parent * 2 + 1; while (end - parent > parent + 1) { if (GT(array + child + 1, array + child)) { ++child; } if (GT(array + child, &temp)) { MOV(array + parent, array + child); parent = child; child = child * 2 + 1; } else { MOV(array + parent, &temp); return; } } if (end == child && GT(array + child, &temp)) { MOV(array + parent, array + child); parent = child; } MOV(array + parent, &temp); } void heapSort2p1(e_type *array, size_t nmemb) { size_t i; e_type temp; if (nmemb > 1) { i = nmemb-- / 2; while (--i != 0) { siftDown2p1(array, i, nmemb); } do { siftDown2p1(array, 0, nmemb); SWAP(array, array + nmemb, &temp); } while (--nmemb != 0); } } /* END ptr_sort.c */ -- pete