Re: offset 1 list indexing

From	cri@tiac.net (Richard Harter)
Newsgroups	comp.lang.c
Subject	Re: offset 1 list indexing
Date	2011-06-29 15:28 +0000
Message-ID	<4e0b3475.471317521@text.giganews.com> (permalink)
References	(12 earlier) <iu5kp1$qk$1@dont-email.me> <4e06aaa8.173880305@text.giganews.com> <4E06C8E2.F3D@mindspring.com> <87d3hx95j9.fsf@bazspaz.fatphil.org> <4E0A9DAB.2DB3@mindspring.com>

Show all headers | View raw

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.

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