[jboss-jira] [JBoss JIRA] Commented: (JBRULES-3141) Replace BinaryHeapPriorityQueue Implementation with Java's PriorityBlockingQueue

[Brad Davis (JIRA)]

    [ https://issues.jboss.org/browse/JBRULES-3141?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12614470#comment-12614470 ] 

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