search

BlueRaja / High-Speed-Priority-Queue-for-C-Sharp

A C# priority queue optimized for pathfinding applications
MIT License
1.15k stars 169 forks source link

Added DequeueMinPriorityItems for simple and fast priority queues. #46

Closed AlexanderSWilliams closed 4 years ago

AlexanderSWilliams commented 5 years ago

This function gives users the ability to pull out all items with the current minimum priority. For a user to implement this correctly in the current version, they must verify the count > 0, get the priority of the first item from First, and Dequeue in a loop. While it is possible for the user to do it, their implementation will be slower than calling DequeueMinPriorityItems.

BlueRaja commented 5 years ago

Is this really a common use-case? What's the utility of this?

AlexanderSWilliams commented 5 years ago

The particular application I'm working on is a SAT solver. I'm working with a notion of cost, and I'm needing to process the lowest cost items in a batch. I would assume that any scheduler that wants to batch items of equal priority concurrently would benefit from this. In hindsight it might make more sense to return an actual queue rather than a list.

As a side note I don't know if it would be possible, but it would be very nice if it is possible to create a version of CascadeDown that takes all the items of the lowest priority at once so that cascading only costs O(log n) time rather than O(m log n) where m is the number of items of the lowest priority. Understandably, even if it is possible, it might not be worth the additional complexity.

On Wed, Jul 17, 2019 at 9:39 PM BlueRaja notifications@github.com wrote:

Is this really a common use-case? What's the utility of this?

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/BlueRaja/High-Speed-Priority-Queue-for-C-Sharp/pull/46?email_source=notifications&email_token=AEFBSTX7UU3OUHMCOKTM4CDP77JULA5CNFSM4IETT522YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOD2HES7Q#issuecomment-512641406, or mute the thread https://github.com/notifications/unsubscribe-auth/AEFBSTQMK7TYQSULLUMAXV3P77JULANCNFSM4IETT52Q .

BlueRaja commented 4 years ago

I tried this out but the difference in speed was negligible, so I've decided not to add it to the API. Sorry!

AlexanderSWilliams commented 4 years ago

I think the performance is going to be more apparent when there's a large number of nodes, but thanks for testing it.

On Wed, Aug 12, 2020 at 9:18 PM BlueRaja notifications@github.com wrote:

I tried this out but the difference in speed was negligible.

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/BlueRaja/High-Speed-Priority-Queue-for-C-Sharp/pull/46#issuecomment-673208853, or unsubscribe https://github.com/notifications/unsubscribe-auth/AEFBSTSV564PPZN46G4JFRTSANEOXANCNFSM4IETT52Q .