search

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

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

Have you considered a partial class for your PriorityQueueNode #6

Closed ferralverrall closed 8 years ago

ferralverrall commented 8 years ago

And then having the FastPriorityQueue be a public class inside the PriorityQueueNode? public partial class PriorityQueueNode { public sealed class FastPriorityQueue<T> : IPriorityQueue<T> where T : PriorityQueueNode {

Then you could make all the PriorityQueue properties { get; protected set;} Won't get a speed increase, just a slight safety increase.

Also, what is the purpose of _numNodesEverEnqueued? if you went to only using _numNodes, I don't see any loss, as once the Queue is cleared, it's safe to start at zero again for insertion index, correct?

Anyway, don't mean to nitpick, I got a nice speed bump by swapping to your Queue over the generics.

BlueRaja commented 8 years ago

Then you'd need to access FastPriorityQueue through PriorityQueueNode: PriorityQueueNode.FastPriorityQueue. Yuck.

_numNodesEverEnqueued is to keep the queue stable, which is necessary in some pathfinding algorithms.

ferralverrall commented 8 years ago

That's what usings are for =) Though I agree, not great, but neither is having public variables that if touched by an outsider, will break the priorityqueue. (Though I could see that being the doctor my elbow hurts problem -- ie, don't do that and everything's fine)

Interesting tidbit about the _numNodesEver thing, which algorithms use it? For my purposes I'm tossing it, downgrading insertionindex to an uint, and priority to a float -- which reminds me do you have a set of performance tests? I'm curious how much I gain (if any) by making the QueueNode smaller, for greater cache coherence. I'm also curious whether there is any speed difference moving to structs.

BlueRaja commented 8 years ago

A stable priority queue is necessary for any algorithm that requires movement to behave in a consistent manner. The example that comes immediately to mind is pathery.com, where ex. if moving both 'up' and 'right' give the same distance, up is always taken.

Though, I suppose I could add a compiler flag (or just create a new PriorityQueue class, StablePriorityQueue, and make the main one non-stable)

BlueRaja commented 8 years ago

(whoops, forgot to answer your other question) - Yes I have a lot of performance tests, but they are a part of the private project this priority queue originally stemmed from.

They are tests of actual pathfinding algorithms (BFS, A, and LPA) against various real-world small- and medium-sized mazes.

BlueRaja commented 8 years ago

I'm going to close this as I'm not going to implement the main suggestion; but I've created #7 for the other suggestion.