Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!gegeweb.42!gegeweb.eu!nntpfeed.proxad.net!proxad.net!feeder1-2.proxad.net!74.125.46.80.MISMATCH!postnews.google.com!news1.google.com!Xl.tags.giganews.com!border1.nntp.dca.giganews.com!nntp.giganews.com!local2.nntp.dca.giganews.com!nntp.earthlink.com!news.earthlink.com.POSTED!not-for-mail NNTP-Posting-Date: Tue, 28 Jun 2011 22:36:07 -0500 Message-ID: <4E0A9DAB.2DB3@mindspring.com> Date: Tue, 28 Jun 2011 23:36:11 -0400 From: pete Reply-To: pfiland@mindspring.com Organization: PF X-Mailer: Mozilla 3.04Gold (WinNT; I) MIME-Version: 1.0 Newsgroups: comp.lang.c Subject: Re: offset 1 list indexing References: <87wrgc8k05.fsf@bazspaz.fatphil.org> <4E06168B.72B2@mindspring.com> <4e062307.139157618@text.giganews.com> <4e06aaa8.173880305@text.giganews.com> <4E06C8E2.F3D@mindspring.com> <87d3hx95j9.fsf@bazspaz.fatphil.org> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Lines: 68 X-Usenet-Provider: http://www.giganews.com NNTP-Posting-Host: 4.154.216.12 X-Trace: sv3-d7ggOP8iqHqLxGTLQF2mSBYWm209xOZurFth49ttf+vU4JfBKGcT0dko/xpYIWThzO5kk6EBIjqGXL6!k5ACRiPyvKYxE4nQldtooyUFra7ca01NWC3JFGSKk+Ixg4ROveYzI0wnXkU5IO+QIcT9TTp9/YdD!ccCz+r+NPA== X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly X-Postfilter: 1.3.40 X-Original-Bytes: 3935 Xref: x330-a1.tempe.blueboxinc.net comp.lang.c:7182 Phil Carmody wrote: > > pete 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