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 00:51:31 -0500
Message-ID: <4E06C8E2.F3D@mindspring.com>
Date: Sun, 26 Jun 2011 01:51:30 -0400
From: pete <pfiland@mindspring.com>
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: <rubrum-E97163.21022514062011@news.albasani.net> <ita0gj$rcp$1@dont-email.me> <rubrum-50B776.15281715062011@news.albasani.net> <itbtln$4bk$1@dont-email.me> <rubrum-5D7959.21424215062011@news.albasani.net> <itcscc$9a1$1@dont-email.me> <rubrum-095E63.23540816062011@news.albasani.net> <87wrgc8k05.fsf@bazspaz.fatphil.org> <kfnsjqxan60.fsf@x-alumni2.alumni.caltech.edu> <4E06168B.72B2@mindspring.com> <4e062307.139157618@text.giganews.com> <iu5eko$nq7$1@dont-email.me> <iu5kp1$qk$1@dont-email.me> <4e06aaa8.173880305@text.giganews.com>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Lines: 165
X-Usenet-Provider: http://www.giganews.com
NNTP-Posting-Host: 4.154.219.253
X-Trace: sv3-qvHnnqTPWP7mMeoe7AiOPIqF4hBY2iUkrJZCEci28VlQ6TUCFD9vTAGbF+WIDESWPnHjUHP5yVYBpvf!EqOyXFg0o6EBw41nigWqejE3zmYD3aqO4WJoNTKimg/AIbGWCoBqQwZdxJwE1F3R0Mp8ylpH6NMu!TcuYzilYng==
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: 5926
Xref: x330-a1.tempe.blueboxinc.net comp.lang.c:6956

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.

http://www.mindspring.com/~pfilandr/C/e_driver/

C:\Program Files\DevStudio\SharedIDE\bin\Debug>e_driver
/* BEGIN e_driver.c program output */

Timing 2 different sorting functions.
Sorting arrays of N number of elements.
The array elements are of type (long unsigned).
sizeof(long unsigned) is 4.
The times shown are in seconds.

Distribution #1: Shuffled
       N     HS2p1       HS2
 1999999  3.406000  2.984000
 2000000  3.422000  3.000000
Total times:
    HS2p1:  6.828000  heapSort2p1
      HS2:  5.984000  heapSort2 casual heap

/* END e_driver.c program output */

C:\Program Files\DevStudio\SharedIDE\bin\Debug>e_driver
/* BEGIN e_driver.c program output */

Counting comparisons and MOV's for 2 different sorting functions.
Sorting arrays of N number of elements.

Distribution #1: Shuffled
       N               HS2p1                 HS2
              CMPS      MOVS      CMPS      MOVS
 1999999  77588742  50097889  81588283  52097055
 2000000  77586900  50095573  81587518  52096641
Total cmps
    HS2p1: 155175642  heapSort2p1
      HS2: 163175801  heapSort2 casual heap
Total movs
    HS2p1: 100193462
      HS2: 104193696

/* END e_driver.c program output */


#include <stddef.h>

#define E_TYPE          long unsigned e_type
#define MOV(A, B)       ((void)(*(A) = *(B)))
#define GT(A, B)        (*(A) > *(B))
#define SWAP(A, B, T)   \
(MOV((T), (A)), MOV((A), (B)), MOV((B), (T)))

typedef E_TYPE;

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);
}

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 
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);
    }
}

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);
    }
}

-- 
pete