Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| Message-ID | <4E0CC851.470F@mindspring.com> (permalink) |
|---|---|
| Date | 2011-06-30 15:02 -0400 |
| From | pete <pfiland@mindspring.com> |
| Organization | PF |
| Newsgroups | comp.lang.c |
| Subject | Re: offset 1 list indexing |
| References | (13 earlier) <4e06aaa8.173880305@text.giganews.com> <4E06C8E2.F3D@mindspring.com> <87d3hx95j9.fsf@bazspaz.fatphil.org> <4E0A9DAB.2DB3@mindspring.com> <4e0b3475.471317521@text.giganews.com> |
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
Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll 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