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" <[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]> > > -- To unsubscribe, e-mail: <mailto:[EMAIL PROTECTED]> For additional commands, e-mail: <mailto:[EMAIL PROTECTED]>
