Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #7015

Re: offset 1 list indexing

Show key headers only | View raw

Richard Harter wrote:
> 
> On Sun, 26 Jun 2011 01:51:30 -0400, pete <pfiland@mindspring.com>
> 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 <stdio.h>
#include <string.h>
#include <stdlib.h>

#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

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

offset 1 list indexing Michael Press <rubrum@pacbell.net> - 2011-06-14 21:02 -0700
  Re: offset 1 list indexing Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-06-14 21:29 -0700
  Re: offset 1 list indexing Nobody <nobody@nowhere.com> - 2011-06-15 05:58 +0100
  Re: offset 1 list indexing Tim Rentsch <txr@alumni.caltech.edu> - 2011-06-15 02:51 -0700
  Re: offset 1 list indexing jacob navia <jacob@spamsink.net> - 2011-06-15 12:01 +0200
    Re: offset 1 list indexing gwowen <gwowen@gmail.com> - 2011-06-15 03:55 -0700
  Re: offset 1 list indexing Mark Bluemel <mark_bluemel@pobox.com> - 2011-06-15 11:07 +0100
    Re: offset 1 list indexing Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-06-15 07:30 -0700
      Re: offset 1 list indexing Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2011-06-15 11:19 -0600
        Re: offset 1 list indexing James Kuyper <jameskuyper@verizon.net> - 2011-06-15 22:57 -0400
        Re: offset 1 list indexing Joseph Huber <joseph.huber@NOREPLY.web.de> - 2011-06-16 09:28 +0200
          Re: offset 1 list indexing Angel <angel+news@spamcop.net> - 2011-06-16 15:05 +0000
          Re: offset 1 list indexing jacob navia <jacob@spamsink.net> - 2011-06-24 01:14 +0200
      Re: offset 1 list indexing Michael Press <rubrum@pacbell.net> - 2011-06-15 15:33 -0700
    Re: offset 1 list indexing Michael Press <rubrum@pacbell.net> - 2011-06-15 15:28 -0700
      Re: offset 1 list indexing Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-06-15 23:34 -0400
        Re: offset 1 list indexing Michael Press <rubrum@pacbell.net> - 2011-06-15 21:42 -0700
          Re: offset 1 list indexing Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-06-16 08:18 -0400
            Re: offset 1 list indexing James Kuyper <jameskuyper@verizon.net> - 2011-06-16 08:32 -0400
              Re: offset 1 list indexing Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-06-16 06:29 -0700
                Re: offset 1 list indexing James Kuyper <jameskuyper@verizon.net> - 2011-06-16 09:43 -0400
              Re: offset 1 list indexing Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-06-16 20:50 -0400
                Re: offset 1 list indexing James Kuyper <jameskuyper@verizon.net> - 2011-06-17 08:56 -0400
                Re: offset 1 list indexing cri@tiac.net (Richard Harter) - 2011-06-17 15:11 +0000
            Re: offset 1 list indexing Michael Press <rubrum@pacbell.net> - 2011-06-16 23:54 -0700
              Re: offset 1 list indexing Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2011-06-23 21:45 +0300
                Re: offset 1 list indexing Tim Rentsch <txr@alumni.caltech.edu> - 2011-06-25 09:30 -0700
                Re: offset 1 list indexing pete <pfiland@mindspring.com> - 2011-06-25 13:10 -0400
                Re: offset 1 list indexing cri@tiac.net (Richard Harter) - 2011-06-25 18:18 +0000
                Re: offset 1 list indexing Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-06-25 15:56 -0400
                Re: offset 1 list indexing James Kuyper <jameskuyper@verizon.net> - 2011-06-25 17:42 -0400
                Re: offset 1 list indexing cri@tiac.net (Richard Harter) - 2011-06-26 04:15 +0000
                Re: offset 1 list indexing pete <pfiland@mindspring.com> - 2011-06-26 01:51 -0400
                Re: offset 1 list indexing cri@tiac.net (Richard Harter) - 2011-06-26 15:48 +0000
                Re: offset 1 list indexing pete <pfiland@mindspring.com> - 2011-06-27 00:30 -0400
                Re: offset 1 list indexing Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2011-06-28 21:26 +0300
                Re: offset 1 list indexing pete <pfiland@mindspring.com> - 2011-06-28 23:36 -0400
                Re: offset 1 list indexing cri@tiac.net (Richard Harter) - 2011-06-29 15:28 +0000
                Re: offset 1 list indexing pete <pfiland@mindspring.com> - 2011-06-30 15:02 -0400
                Re: offset 1 list indexing Ike Naar <ike@sverige.freeshell.org> - 2011-06-26 07:00 +0000
                Re: offset 1 list indexing cri@tiac.net (Richard Harter) - 2011-06-26 15:20 +0000
                Re: offset 1 list indexing cri@tiac.net (Richard Harter) - 2011-06-26 03:41 +0000
                Re: offset 1 list indexing Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-06-26 08:51 -0400
                Re: offset 1 list indexing cri@tiac.net (Richard Harter) - 2011-06-26 15:32 +0000
                Re: offset 1 list indexing Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-06-26 11:48 -0400
                Re: offset 1 list indexing cri@tiac.net (Richard Harter) - 2011-06-26 16:43 +0000
                Re: offset 1 list indexing Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2011-06-28 21:30 +0300
                Re: offset 1 list indexing Karl Malbrain <malbrain@yahoo.com> - 2011-06-28 14:13 -0700
                Re: offset 1 list indexing Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2011-06-28 21:14 +0300
                Re: offset 1 list indexing Tim Rentsch <txr@alumni.caltech.edu> - 2011-06-29 01:14 -0700
  Re: offset 1 list indexing Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-06-15 07:21 -0400
  Re: offset 1 list indexing Shao Miller <sha0.miller@gmail.com> - 2011-06-15 10:09 -0400
    Re: offset 1 list indexing Michael Press <rubrum@pacbell.net> - 2011-06-15 15:38 -0700
  Re: offset 1 list indexing China Blue Dolls <chine.bleu@yahoo.com> - 2011-06-25 21:04 -0700
    Re: offset 1 list indexing Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-06-26 09:01 -0400
    Re: offset 1 list indexing Michael Press <rubrum@pacbell.net> - 2011-06-26 13:15 -0700

csiph-web