On Wed, 14 Nov 2001 00:47, Chad Stansbury wrote: > 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.
great! > > Thanks, Chad > > ----- Original Message ----- > From: "Peter Donald" <[EMAIL PROTECTED]> > To: "Avalon Developers List" <[EMAIL PROTECTED]> > 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" <[EMAIL PROTECTED]> > > > To: "Avalon Developers List" <[EMAIL PROTECTED]> > > > 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:[EMAIL PROTECTED]> > > > > > > > For additional commands, e-mail: > > > > > > <mailto:[EMAIL PROTECTED]> > > > > -- > > 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:[EMAIL PROTECTED]> > > > For additional commands, e-mail: > > <mailto:[EMAIL PROTECTED]> -- Cheers, Pete ----------------------------------------------------------------------- | I thought there was a knob on the TV to turn up the intelligence. | | There's a knob called "brightness", but it doesn't work. | ----------------------------------------------------------------------- -- To unsubscribe, e-mail: <mailto:[EMAIL PROTECTED]> For additional commands, e-mail: <mailto:[EMAIL PROTECTED]>
