avalon-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Chad Stansbury" <stansbu...@earthlink.net>
Subject Re: [Excalibur] PriorityQueue & BinaryHeap proposal
Date Tue, 13 Nov 2001 13:47:17 GMT
I will download your changes and test them.  Luckily I have a bunch of tests
from my own n-ary heap class that I can modify and use to test this version.
Once I'm finished I'll upload the test driver to this list.

Thanks, Chad

----- Original Message -----
From: "Peter Donald" <donaldp@apache.org>
To: "Avalon Developers List" <avalon-dev@jakarta.apache.org>
Sent: Tuesday, November 13, 2001 2:54 AM
Subject: Re: [Excalibur] PriorityQueue & BinaryHeap proposal


> Okay. I added the patch with a few changes. Essentially you had made some
> methods protected when they were previously private. I changed them back
to
> private.
>
> I also readded a few constructors that were in the last version (the ones
> that took a boolean indicating whether it was a maximum or minimum heap).
> This was mainly to minimize the change in interface between the two
versions.
>
> I also added you as an author tag.
>
> Anyways could you download it from CVS and make sure I didn't stuff
anything
> up ? ;)
>
> Unfortunately we don't have a unit test for the PriorityHeap and we really
> should have one.
>
> On Thu, 8 Nov 2001 11:58, Chad Stansbury wrote:
> > Attached are the files that I have patched to allow the priority queue,
> > synchronized priority queue, and binary heap to accept Objects rather
than
> > Comparables.  Note that these patches do not retain backwards
> > compatibility. You will find that the following major implementation
> > changes were made:
> >
> > 1. All references to Comparable have been changed to Object
> > 2. I have substituted a Comparator for the isMinHeap parameter.  The
> > BinaryHeap now has two constants - MAX_COMPARATOR and MIN_COMPARATOR.
> > These comparators assume that the elements stored in the heap implement
the
> > Comparable interface. If you don't specify a comparator in the
constructor,
> > it defaults to MIN_COMPARATOR, thereby yielding a min heap.  If you want
a
> > max heap, you specify MAX_COMPARATOR in the constructor.  You can also
> > specify a custom comparator if you don't want to rely on the content's
> > natural ordering.
> > 3. I have consolidated the separate percolateDown/Up Min and Max heap
> > methods.  Instead there is now just a single percolateDownHeap and
> > percolateUpHeap method that utilizes the comparator to determine the
> > ordering.
> > 4. I have made 2 performance related changes:
> > 4a. I have removed a redundant divide and multiply statement in the
while
> > loop for the two percolate methods.  This resulted in a 4% speed
increase.
> > 4b. I have changed 'hole * 2' and 'hole / 2' to 'hold << 1' and 'hold >>
> > 1', respectively.  I would have thought the java compiler would perform
> > this optimization for me, but alas, jdk 1.3.1 does not appear to do so.
> > Anyhow, this seems to increase the speed of the insert operation by a
> > non-trivial amount.
> >
> > Unfortunately, the new implementation degrades the pop performance
> > somewhat. I have seen about a 9% performance hit when inserting and
popping
> > 2,000,000 random Integers into the heap (14,971 ms for the old
> > implementation vs. 16,414 ms using the new implementation).  This
> > performance degradation can be attributed to the additional method call
and
> > cast involved with using a Comparator rather than directly invoking the
> > element's compareTo method.
> >
> > All performance measurements were recording on a 1.4 GHz P4 running
> > jdk1.3.1_01 on Win2K.
> >
> > ----- Original Message -----
> > From: "Peter Donald" <donaldp@apache.org>
> > To: "Avalon Developers List" <avalon-dev@jakarta.apache.org>
> > Sent: Wednesday, November 07, 2001 7:49 AM
> > Subject: Re: [Excalibur] PriorityQueue & BinaryHeap proposal
> >
> > > On Thu, 8 Nov 2001 01:04, Chad Stansbury wrote:
> > > > Okay - here's the problem.  The current BinaryHeap interface expects
a
> > > > Comparable for it's public interface.  In order to maintain
backwards
> > > > compatibility I must either:
> > > >
> > > > 1. Add new public methods to the BinaryHeap class (e.g.,
insertObject,
> > > > peekObject, popObject) and change the insert, peek, and pop methods
to
> > > > invoke these new methods, or
> > > > 2. I can create a new BinaryObjectHeap class and have the BinaryHeap
> >
> > class
> >
> > > > act as a wrapper class.
> > > >
> > > > I am also wondering how I would modify the PriorityQueue interface
w/o
> > > > breaking backwards compatibility...
> > > >
> > > > Any suggestions would be appreciated.
> > >
> > > I am not sure we need to maintain 100% backwards compatability in this
> >
> > case.
> >
> > > peek() and pop() methods in al cases that I use them and have seen
them
> >
> > used
> >
> > > will actually need to be cast to something else anyways. Retrieving a
> > > Comparable from heap is rarely the aim and come to think of it I think
it
> >
> > was
> >
> > > probably a mistake to return Comparables rather than Objects ;)
> > >
> > > For insert there will need to be backwards compatability because
people
> >
> > will
> >
> > > use that to pass in comparables. However you should be ab;le to get
> >
> > backwards
> >
> > > compatability with this by just checking the type passed in (if
> > > Comparable
> >
> > do
> >
> > > X, else do Y) and converting parameter to Object.
> > >
> > > --
> > > Cheers,
> > >
> > > Pete
> > >
> > > --------------------------------------------------------------
> > > "Science is like sex: sometimes something useful comes out,
> > > but that is not the reason we are doing it" -- Richard Feynman
> > > --------------------------------------------------------------
> > >
> > > --
> > > To unsubscribe, e-mail:
> >
> > <mailto:avalon-dev-unsubscribe@jakarta.apache.org>
> >
> > > For additional commands, e-mail:
> >
> > <mailto:avalon-dev-help@jakarta.apache.org>
>
> --
> Cheers,
>
> Pete
>
> ---------------------------------------------------
> "It is easy to dodge our responsibilities, but we
> cannot dodge the consequences of dodging our
> responsibilities." -Josiah Stamp
> ---------------------------------------------------
>
> --
> To unsubscribe, e-mail:
<mailto:avalon-dev-unsubscribe@jakarta.apache.org>
> For additional commands, e-mail:
<mailto:avalon-dev-help@jakarta.apache.org>
>
>


--
To unsubscribe, e-mail:   <mailto:avalon-dev-unsubscribe@jakarta.apache.org>
For additional commands, e-mail: <mailto:avalon-dev-help@jakarta.apache.org>


Mime
View raw message