Closed alibad closed 8 years ago
BlueRaja
commented
8 years ago There is definitely a way to do this and get the same performance without that extreme coupling.
No, there isn't. Have you read this?
That being said, I have created an implementation which is safer and easier to use (safety checks in the release version, thread-safe, enqueues any object), but haven't had time to test and release it yet. I will try to get around to that soon.
alibad
commented
8 years ago Ok, that adds some more context. But still...
Let me give you this very simple example. I have an int. Now I have to create an IntWrapper class, make it inherit from your class, take the cost of storing all the 3 extra properties (double, long, long), take in the extra cost of allocation, with the added disadvantage of complexity. Too much overhead for what someone would be looking for in a priority queue.
A priority queue is mainly used to enqueue and dequeue by priority (Min heap or max heap), not to check if the queue contains a certain value. You implementation is not improving performance of expected operations on a priority queue (in fact it's slightly adding a bit perf\memory overhead on those operations). If you want to optimize for lookup, just use a different data structure.
BlueRaja
commented
8 years ago A normal priority queue will have the exact same overhead, it will just be hidden from you (at the cost of a small amount of speed).
This priority queue was originally written to be as fast as humanly possible for path-finding applications specifically, so enqueuing primitives wasn't an initial design consideration. However, as I said above, I've now written a more widely-applicable implementation, I just need to find time to test and publish it.
BlueRaja
commented
8 years ago I've pushed what I have so far to the SafePriorityQueue branch. The 'fast' queue has been renamed to FastPriorityQueue, while the 'convenient' queue is SafePriorityQueue.
Please be aware that some behavior is liable to change (eg. I'm not sure if I want First to return null or throw an exception when the queue is empty; or if duplicate keys should be allowed in SafePriorityQueue since they cannot be allowed in FastPriorityQueue)
BlueRaja
commented
8 years ago I've completed the implementation and created a PR: #2. Would you like to test it out before I merge?
BlueRaja
commented
8 years ago PR has been merged! The new implementation is called SimplePriorityQueue. It doesn't have the coupling issues, it automatically resizes, it contains lots of safety checks, and it's thread-safe.
The original priority queue has been renamed to FastPriorityQueue.
alibad
commented
8 years ago Hi Raja,
Sorry I haven't been able to respond and review. Glad to see the improvements!
Sent from my Phone
On Jan 4, 2016, at 3:01 AM, BlueRaja notifications@github.com wrote:
PR has been merged! The new implementation is called SimplePriorityQueue. It doesn't have the coupling issues, it automatically resizes, it contains lots of safety checks, and it's thread-safe.
— Reply to this email directly or view it on GitHub.
This implementation of the priority queue wouldn't work well with objects in external libraries. It will also stain business objects with data-structure-related methods and properties.
If I want to put an object in this queue, it has to inherit from PriorityQueueNode. This makes any objects I want to put in the queue very tightly coupled with the queue data structure. There is definitely a way to do this and get the same performance without that extreme coupling.