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

Priority type generalization #16

Closed electromax closed 7 years ago

electromax commented 7 years ago

BlueRaja created a great priority queue library for .NET which style I really like. However, I was surprised that only the type of queue elements (T) is generalized as in "xxxPriorityQueue of T", while the priorities must be "float" numbers. That limits the library's usage. I changed the library so that the type of priority value is arbitrary, given that it is IComparable, as in "xxxPriorityQueue of T, K". Please approve my pull request to the main repository.

BlueRaja commented 7 years ago

Is there a performance hit to FastPriorityQueue? If so I won't be merging this. However, I would be interested in adding generics to SimplePriorityQueue.

BlueRaja commented 7 years ago

I'm going to close this because I measured it to cause a ~5% slowdown. However I'm going to basically reimplement this in a new class and use that to make SimplePriorityQueue (at least) generic.

electromax commented 7 years ago

I am not sure how and with which key type the slowdown was measured. I don't believe adding the second type argument to a class which is already generic costs more resources than the operations to cast arbitrary key comparable type (like DateTime) to "float" anytime an element is added or its priority changes. For some key types, e.g. strings, such cast is not realistic at all. It's your decision after all to not merge. Thank you for your work. Maksim

BlueRaja commented 7 years ago

I don't believe adding the second type argument to a class which is already generic costs more resources than the operations to cast arbitrary key comparable type (like DateTime) to "float"

Most users will not be casting arbitrary comparable types to float, so that point is moot. The cost comes from having to use CompareTo() instead of <.