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

Groups > comp.lang.c > #6092 > unrolled thread

offset 1 list indexing

Back to article view | Back to comp.lang.c

Contents

  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

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

#6154

On 06/16/2011 09:29 AM, Malcolm McLean wrote:
...
> If you're working with a mixture of C and Fortran you often have to
> simultaneously convert between row-major to column-major, and offset
> the arrays. It's too much.

I know, I've done it. It's not too much to do, but it's too much to do
without a good reason.
-- 
James Kuyper

[toc] | [prev] | [next] | [standalone]

#6207

On 6/16/2011 8:32 AM, James Kuyper wrote:
> On 06/16/2011 08:18 AM, Eric Sosman wrote:
>> [...]
>>       And converting between a one-based index and an N-based
>> index *is* simple arithmetic.
>
> That the transformation can be done, and even that it's easy, doesn't
> mean that it's a good idea to perform it. That it's not necessarily a
> transformation worth performing, means that it's just plain ridiculous
> to misinterpret a refusal to perform it as indicating an inability to
> perform it.

     "Heaps" was advanced, and I believe advanced sincerely, as a
reason to rely on one-based array indexing.  That's nonsense.

-- 
Eric Sosman
esosman@ieee-dot-org.invalid

[toc] | [prev] | [next] | [standalone]

#6230

On 06/16/2011 08:50 PM, Eric Sosman wrote:
> On 6/16/2011 8:32 AM, James Kuyper wrote:
>> On 06/16/2011 08:18 AM, Eric Sosman wrote:
>>> [...]
>>>       And converting between a one-based index and an N-based
>>> index *is* simple arithmetic.
>>
>> That the transformation can be done, and even that it's easy, doesn't
>> mean that it's a good idea to perform it. That it's not necessarily a
>> transformation worth performing, means that it's just plain ridiculous
>> to misinterpret a refusal to perform it as indicating an inability to
>> perform it.
> 
>      "Heaps" was advanced, and I believe advanced sincerely, as a
> reason to rely on one-based array indexing.  That's nonsense.

That's too vague, in that it depends upon what you mean by "reason to
rely on". If it was given a an example of code that's easier to write,
read, and understand when using one-based indexing, that's entirely
possible (though I cannot vouch for whether or not it's true), and no
one has suggested anything stronger than that in this thread. If, on the
other hand, they suggested that it COULD NOT be implemented with 0-based
indexing, that would be, as you say, "nonsense".
-- 
James Kuyper

[toc] | [prev] | [next] | [standalone]

#6245

On Fri, 17 Jun 2011 08:56:58 -0400, James Kuyper
<jameskuyper@verizon.net> wrote:

>On 06/16/2011 08:50 PM, Eric Sosman wrote:
>> On 6/16/2011 8:32 AM, James Kuyper wrote:
>>> On 06/16/2011 08:18 AM, Eric Sosman wrote:
>>>> [...]
>>>>       And converting between a one-based index and an N-based
>>>> index *is* simple arithmetic.
>>>
>>> That the transformation can be done, and even that it's easy, doesn't
>>> mean that it's a good idea to perform it. That it's not necessarily a
>>> transformation worth performing, means that it's just plain ridiculous
>>> to misinterpret a refusal to perform it as indicating an inability to
>>> perform it.
>> 
>>      "Heaps" was advanced, and I believe advanced sincerely, as a
>> reason to rely on one-based array indexing.  That's nonsense.
>
>That's too vague, in that it depends upon what you mean by "reason to
>rely on". If it was given a an example of code that's easier to write,
>read, and understand when using one-based indexing, that's entirely
>possible (though I cannot vouch for whether or not it's true), and no
>one has suggested anything stronger than that in this thread. If, on the
>other hand, they suggested that it COULD NOT be implemented with 0-based
>indexing, that would be, as you say, "nonsense".

The code for in-place heaps is (slightly) simpler with one-based
indexing.  In 0-based indexing the children of node n are at nodes
(2*n+1,2*n+2, in 1-based indexing they are at (2*n,2*n+1).  It's not a
big deal but the resulting code is a bit easier to read, write, and
debug.

 

[toc] | [prev] | [next] | [standalone]

#6223

In article <itcscc$9a1$1@dont-email.me>,
 Eric Sosman <esosman@ieee-dot-org.invalid> wrote:

> On 6/16/2011 12:42 AM, Michael Press wrote:
> > In article<itbtln$4bk$1@dont-email.me>,
> >   Eric Sosman<esosman@ieee-dot-org.invalid>  wrote:
> >
> >> On 6/15/2011 6:28 PM, Michael Press wrote:
> >>> In article<ita0gj$rcp$1@dont-email.me>,
> >>>    Mark Bluemel<mark_bluemel@pobox.com>   wrote:
> >>>
> >>>> On 06/15/2011 05:02 AM, Michael Press wrote:
> >>>>> I want to index into a list using offset one indexing.
> >>>>
> >>>> Why?
> >>>
> >>> Why not? But to humor you: heaps.
> >>
> >>       A few months ago, I offered heaps as an example of how some
> >> programmers couldn't do simple index transformations, and were
> >> unable to write zero-based implementations.
> >>
> >>       Somewhat to my dismay, a few "programmers" in this group did
> >> in fact maintain that it was "too difficult" or "too confusing" or
> >> "too unnatural" to implement heaps in zero-based arrays.
> >>
> >>       Ye.  Flipping.  Gods.
> >>
> >>       "Programmers" who can't do simple arithmetic.
> >>
> >>       Ye.  Flipping.  Gods.
> >
> > You've gone off the deep end. Get a grip;
> > or else tell me straight on I do not know
> > how to do simple arithmetic.
> 
>      Were you the person in that old thread who maintained that
> heaps couldn't/wouldn't/shouldn't be implemented with anything
> other than 1-based arrays?  

Was I?

-- 
Michael Press

[toc] | [prev] | [next] | [standalone]

#6750

Michael Press <rubrum@pacbell.net> writes:
> In article <itcscc$9a1$1@dont-email.me>,
>  Eric Sosman <esosman@ieee-dot-org.invalid> wrote:
> 
> > On 6/16/2011 12:42 AM, Michael Press wrote:
> > > In article<itbtln$4bk$1@dont-email.me>,
> > >   Eric Sosman<esosman@ieee-dot-org.invalid>  wrote:
> > >
> > >> On 6/15/2011 6:28 PM, Michael Press wrote:
> > >>> In article<ita0gj$rcp$1@dont-email.me>,
> > >>>    Mark Bluemel<mark_bluemel@pobox.com>   wrote:
> > >>>
> > >>>> On 06/15/2011 05:02 AM, Michael Press wrote:
> > >>>>> I want to index into a list using offset one indexing.
> > >>>>
> > >>>> Why?
> > >>>
> > >>> Why not? But to humor you: heaps.
> > >>
> > >>       A few months ago, I offered heaps as an example of how some
> > >> programmers couldn't do simple index transformations, and were
> > >> unable to write zero-based implementations.
> > >>
> > >>       Somewhat to my dismay, a few "programmers" in this group did
> > >> in fact maintain that it was "too difficult" or "too confusing" or
> > >> "too unnatural" to implement heaps in zero-based arrays.
> > >>
> > >>       Ye.  Flipping.  Gods.
> > >>
> > >>       "Programmers" who can't do simple arithmetic.
> > >>
> > >>       Ye.  Flipping.  Gods.
> > >
> > > You've gone off the deep end. Get a grip;
> > > or else tell me straight on I do not know
> > > how to do simple arithmetic.
> > 
> >      Were you the person in that old thread who maintained that
> > heaps couldn't/wouldn't/shouldn't be implemented with anything
> > other than 1-based arrays?  
> 
> Was I?

If '/' represents selection rather than aggregation, then it 
was probably me. I certainly *wouldn't* implement then 0-based
unless there was an extraordinary reason to do that. I've yet
to encounter such a reason.  Having said that, looking at the
prior replies in this thread, several other people have said
that too, so there's no guarantee it was me. 0-based heaps 
have carbunkles. End of.

Phil
-- 
"At least you know where you are with Microsoft."
"True. I just wish I'd brought a paddle." -- Matthew Vernon

[toc] | [prev] | [next] | [standalone]

#6931

Phil Carmody <thefatphil_demunged@yahoo.co.uk> writes:

> [discussing 1-origin arrays versus 0-origin arrays]
>
> 0-based heaps have carbunkles. End of.

Please excuse my temerity, but I think you are too good
a programmer for this to be true.  Take a run at writing
a 0-based heap, not just dashing it off but really trying
to do a good clean job, and see if it comes out better
than you expect.  I will if you will.

[toc] | [prev] | [next] | [standalone]

#6933

Tim Rentsch wrote:
> 
> Phil Carmody <thefatphil_demunged@yahoo.co.uk> writes:
> 
> > [discussing 1-origin arrays versus 0-origin arrays]
> >
> > 0-based heaps have carbunkles. End of.
> 
> Please excuse my temerity, but I think you are too good
> a programmer for this to be true.  Take a run at writing
> a 0-based heap, not just dashing it off but really trying
> to do a good clean job, and see if it comes out better
> than you expect.  I will if you will.

I don't see what the problem is with 0 based heaps.

Not being able to write C code without 1 based arrays
is like not be able to ride a bicycle without training wheels.

-- 
pete

[toc] | [prev] | [next] | [standalone]

#6935

On Sat, 25 Jun 2011 13:10:35 -0400, pete <pfiland@mindspring.com>
wrote:

>Tim Rentsch wrote:
>> 
>> Phil Carmody <thefatphil_demunged@yahoo.co.uk> writes:
>> 
>> > [discussing 1-origin arrays versus 0-origin arrays]
>> >
>> > 0-based heaps have carbunkles. End of.
>> 
>> Please excuse my temerity, but I think you are too good
>> a programmer for this to be true.  Take a run at writing
>> a 0-based heap, not just dashing it off but really trying
>> to do a good clean job, and see if it comes out better
>> than you expect.  I will if you will.
>
>I don't see what the problem is with 0 based heaps.

It's slightly awkward.  In a 0 based heap the children of node n are
at nodes 2*n+1 and 2*n+2.  The parent of node n is at (n-1)/2.  In a 1
based heap the children of node n are at 2*n and 2*n+2; the parent of
node n is at n/2.
>
>Not being able to write C code without 1 based arrays
>is like not be able to ride a bicycle without training wheels.

True.  Then again, civilized languages let you select the array base
to suit the problem.

[toc] | [prev] | [next] | [standalone]

#6938

On 6/25/2011 2:18 PM, Richard Harter wrote:
> On Sat, 25 Jun 2011 13:10:35 -0400, pete<pfiland@mindspring.com>
> wrote:
>> [...]
>> Tim Rentsch wrote:
>>> [...]
>> I don't see what the problem is with 0 based heaps.
>
> It's slightly awkward.  In a 0 based heap the children of node n are
> at nodes 2*n+1 and 2*n+2.  The parent of node n is at (n-1)/2.  In a 1
> based heap the children of node n are at 2*n and 2*n+2; the parent of
> node n is at n/2.

     Tastes vary, but I prefer correct awkwardness to graceful error.

>> Not being able to write C code without 1 based arrays
>> is like not be able to ride a bicycle without training wheels.
>
> True.  Then again, civilized languages let you select the array base
> to suit the problem.

     It's a poor workman who blames his tools.

-- 
Eric Sosman
esosman@ieee-dot-org.invalid

[toc] | [prev] | [next] | [standalone]

#6940

On 06/25/2011 03:56 PM, Eric Sosman wrote:
> On 6/25/2011 2:18 PM, Richard Harter wrote:
>> On Sat, 25 Jun 2011 13:10:35 -0400, pete<pfiland@mindspring.com>
...
>>> Not being able to write C code without 1 based arrays
>>> is like not be able to ride a bicycle without training wheels.
>>
>> True.  Then again, civilized languages let you select the array base
>> to suit the problem.
> 
>      It's a poor workman who blames his tools.

That's true - but only insofar as good workmen accept responsibility for
choosing the right tool for a job, and for making sure that it's in good
working condition. The assertion that a given tool is not in good
condition, or is not the right one for a given job is (if correct) a
sign of competence, not incompetence.

I wouldn't value the ability to adjust the array base quite as highly as
he did, but that's a judgment call that may reflect the fact that I have
more, and more recent, experience with C than with Fortran.
-- 
James Kuyper

[toc] | [prev] | [next] | [standalone]

#6952

On Sat, 25 Jun 2011 17:42:56 -0400, James Kuyper
<jameskuyper@verizon.net> wrote:

>On 06/25/2011 03:56 PM, Eric Sosman wrote:
>> On 6/25/2011 2:18 PM, Richard Harter wrote:
>>> On Sat, 25 Jun 2011 13:10:35 -0400, pete<pfiland@mindspring.com>
>...
>>>> Not being able to write C code without 1 based arrays
>>>> is like not be able to ride a bicycle without training wheels.
>>>
>>> True.  Then again, civilized languages let you select the array base
>>> to suit the problem.
>> 
>>      It's a poor workman who blames his tools.
>
>That's true - but only insofar as good workmen accept responsibility for
>choosing the right tool for a job, and for making sure that it's in good
>working condition. The assertion that a given tool is not in good
>condition, or is not the right one for a given job is (if correct) a
>sign of competence, not incompetence.
>
>I wouldn't value the ability to adjust the array base quite as highly as
>he did, but that's a judgment call that may reflect the fact that I have
>more, and more recent, experience with C than with Fortran.

You may have more experience with modern Fortran than I do - my last
Fortran program was written in 1982.  However I try to keep up with
what different languages are doing, even Fortran.  As it happens
modern Fortran, along with a lot of other languages, lets one adjust
array bases.  

The problem (if it matters) in C is that arrays are second class
citizens.  As a result there are a lot of things that are awkward in C
if they are expressed in terms of arrays.

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.

In other words, if you want to do one based indexing and you're
willing to discard a location, you do something like:

a = malloc((n+1)*sizeof(node));  /* Yes, Keith I know you don't need
                                    parentheses for sizeof.  */
heap = a+1;

So far, so good.  When you free the space, you must remember that the
allocation address is heap-1.  It's a good opportunity for bugs.  Not
a problem for good workmen who never blame their tools, but a trap,
none-the-less.  Actually it's not a problem if you wrap your heap in
an ADT package but that's another story.

  

[toc] | [prev] | [next] | [standalone]

#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

[toc] | [prev] | [next] | [standalone]

#6973

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?  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.

[toc] | [prev] | [next] | [standalone]

#7015

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

[toc] | [prev] | [next] | [standalone]

#7159

pete <pfiland@mindspring.com> 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.

> 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.

Phil
-- 
"At least you know where you are with Microsoft."
"True. I just wish I'd brought a paddle." -- Matthew Vernon

[toc] | [prev] | [next] | [standalone]

#7182

Phil Carmody wrote:
> 
> pete <pfiland@mindspring.com> 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.
> 
> > 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.

But that's not the point.
I dislike 1 based arrays 
because they remind me of neophytes 
who are confused by things like pointers
and who can't grok things like 0 based arrays.

I brought up the casual heapsort
because I like to discuss sorting
and it seemed topical to Richard Harter's
preference for simpler arithmetic calculations 
of the location of the children nodes,
for which he acknowledged 
that there might be alternative ways of achieving
besides using 1 based arrays.

I forgot to mention that I only get faster times
for large arrays of integers using the casual heap.
For small arrays of 
 (I forget exactly but I think the turning point 
  is at somewhere around 200 elements),
integers, and for arrays of any size of slower data types,
I get slower times with the casual heapsort
on the C implementation that I am using.

-- 
pete

[toc] | [prev] | [next] | [standalone]

#7210

On Tue, 28 Jun 2011 23:36:11 -0400, pete <pfiland@mindspring.com>
wrote:

>Phil Carmody wrote:
>> 
>> pete <pfiland@mindspring.com> 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.

>
>But that's not the point.
>I dislike 1 based arrays 
>because they remind me of neophytes 
>who are confused by things like pointers
>and who can't grok things like 0 based arrays.

It's a viewpoint.  

>
>I brought up the casual heapsort
>because I like to discuss sorting
>and it seemed topical to Richard Harter's
>preference for simpler arithmetic calculations 
>of the location of the children nodes,
>for which he acknowledged 
>that there might be alternative ways of achieving
>besides using 1 based arrays.

>
>I forgot to mention that I only get faster times
>for large arrays of integers using the casual heap.
>For small arrays of 
> (I forget exactly but I think the turning point 
>  is at somewhere around 200 elements),
>integers, and for arrays of any size of slower data types,
>I get slower times with the casual heapsort
>on the C implementation that I am using.

That's interesting.  I can see that there would be a problem with
slower data types - you are doing some extra compares and moves which
are more expensive than the fiddly arithmetic.  But I don't quite see
why the "casual heap" would be more efficient.  One speculation is
that the cost of address calculation actually makes a difference.
Another is that your code always keeps the two largest elements in the
cache which may make a difference.

[toc] | [prev] | [next] | [standalone]

#7318

Richard Harter wrote:
> 
> On Tue, 28 Jun 2011 23:36:11 -0400, pete <pfiland@mindspring.com>
> wrote:
> 
> >Phil Carmody wrote:
> >>
> >> pete <pfiland@mindspring.com> 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 <stdio.h>
#include <string.h>

#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

[toc] | [prev] | [next] | [standalone]

#6960

On 2011-06-26, Richard Harter <cri@tiac.net> wrote:
> In other words, if you want to do one based indexing and you're
> willing to discard a location, you do something like:
>
> a = malloc((n+1)*sizeof(node));  /* Yes, Keith I know you don't need
>                                     parentheses for sizeof.  */

In the above case, you do need them; you can re-write it as

    a = malloc((n+1) * sizeof *a);

and then you don't need them.

> heap = a+1;

I don't follow; if ``heap'' is supposed to be one-based, wouldn't
it simply be:

    heap = malloc((n+1) * sizeof *heap);  /* or ... sizeof(node) */
 
and then ignore heap[0], use heap[1..n], and free(heap) when done?

[toc] | [prev] | [next] | [standalone]

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

Back to top | Article view | comp.lang.c

csiph-web