[jboss-jira] [JBoss JIRA] Commented: (JBRULES-3141) Replace BinaryHeapPriorityQueue Implementation with Java's PriorityBlockingQueue
[
https://issues.jboss.org/browse/JBRULES-3141?page=com.atlassian.jira.plug...
]
Brad Davis commented on JBRULES-3141:
-------------------------------------
I have written a implementation that takes into account the following:
The number of different saliences should not be large in comparison to the number of
activations themselves.
If N is the total number of activations...
Before, the running time was essentially O ( log n ) for add and remove as the heap would
have to be adjusted.
Now, I consider each salience a separate bucket. So there may be N activations, but maybe
a very small number of saliences S.
Now, the worst running time should be O ( log S ) + O ( 1 ).
Replace BinaryHeapPriorityQueue Implementation with Java's
PriorityBlockingQueue
--------------------------------------------------------------------------------
Key: JBRULES-3141
URL: https://issues.jboss.org/browse/JBRULES-3141
Project: Drools
Issue Type: Feature Request
Security Level: Public(Everyone can see)
Reporter: Brad Davis
Assignee: Brad Davis
Attachments: BasePriorityQueue.java, BinaryHeapPriorityQueueTest.java,
IndexAwareQueue.java, SalienceAwareQueue.java
Attached is a PriorityQueue implementation I wrote last night to replace our home grown
implementation. I think it must have preceded the PriorityBlockingQueue that is already
part of Java 5 & 6.
BinaryHeapPriorityQueueTest is where I plugged in this implementation. Below are the
results first running with our home grown BinaryHeapPriorityQueue, and then with the one I
created, BasePriorityQueue. There are numerous other benefits to using this as well, as
it will fully implement the java.util.Collections API and therefore cleanup some other
code elsewhere in our codebase.
The result for 10000 objects inserted and retracted was:
BinaryHeapPriortyQueue
elapsedEnqueue = 32
elapsedDequeue = 294
BasePriorityQueue
elapsedEnqueue = 26
elapsedDequeue = 167
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira