Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| Message-ID | <4E0A9DAB.2DB3@mindspring.com> (permalink) |
|---|---|
| Date | 2011-06-28 23:36 -0400 |
| From | pete <pfiland@mindspring.com> |
| Organization | PF |
| Newsgroups | comp.lang.c |
| Subject | Re: offset 1 list indexing |
| References | (11 earlier) <iu5eko$nq7$1@dont-email.me> <iu5kp1$qk$1@dont-email.me> <4e06aaa8.173880305@text.giganews.com> <4E06C8E2.F3D@mindspring.com> <87d3hx95j9.fsf@bazspaz.fatphil.org> |
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
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