TPriorityQueue for Delphi?
TPriorityQueue for Delphi?
Does anyone know of an efficient implementation of a Priority Queue for Delphi (ideally using generics)? There seems to be a couple of old libraries (e.g. SysTools and EZDSL), which I don't think use Generics and I'm not confident will be kept up to date.
What I'd like is a TPriorityQueue which has a comparator and takes care of keeping the queue in order.
I'm a little surprise System.Generics.Collections doesn't have it
- Steve
Does anyone know of an efficient implementation of a Priority Queue for Delphi (ideally using generics)? There seems to be a couple of old libraries (e.g. SysTools and EZDSL), which I don't think use Generics and I'm not confident will be kept up to date.
What I'd like is a TPriorityQueue
I'm a little surprise System.Generics.Collections doesn't have it
- Steve
Yeah been wanting one of these myself from time to time.
ReplyDeleteIt's not trivial, as there are many concerns. Do you need to prevent something remaining at the end of the queue, ie starvation? Basically it is a fifo with reweighting and reordering on insert.
ReplyDeleteNeeded a diversion so I adapted an (MIT) open-source one for C# I found. I'll add some unit tests and push it to github tomorrow.
ReplyDeleteLars Fosdal efficiently inserting a new entry into a sorted list is not trivial.
ReplyDeleteAsbjørn Heid looking forward to seeing what you have for us!
ReplyDelete/sub
ReplyDeleteSteve Maughan and if you add multiple consumers and restrictions on what tasks that can run in parallel, and what tasks must be run in sequence, that really adds to the fun.
ReplyDeleteLars Fosdal Sounds like you're talking more of a scheduler than a priority queue.
ReplyDeleteYeah, I have one :D Let me search here on my files :D It is generic but not thread-safe.
ReplyDeletehttps://github.com/lordcrc/DGPQueue
ReplyDeleteIt's stable, meaning elements of same priority is dequeued FIFO, at the cost of a 64bit counter per element. I might refactor that so the stability is optional.
Two versions are present, one which has a single element type E, but allows for two different comparators: element comparator and priority comparator. The former is used for equality comparison to locate elements in the queue, the latter is used for determining ordering. It's using a min-heap, so elements which compare lower in terms of priority are further up the top of the queue.
The second version is a conveninence type which allows for a separate priority type P, so you could have say an "external" priority for each element.
The "plain" enumerator is un-ordered, there's also a DequedElements enumerable which enumerator will dequeue elements as it is enumerated. A sorted (non-dequeueing) enumerator would be nice, so may add that later.
It also has Contains() and Remove() methods, for checking if an element exists in the queue and removing an arbitrary element in the queue, respectively.
I went with records for the public API mainly due to operator overloading (especially "in" operator), but I might just revert to plain interfaces.
Ideally I'd use TList to hold the elements of the heap, as it's swap logic should be more performant, but I'll wait until the dust has settled from the massive rewrite.
ReplyDeleteAsbjørn Heid You were right. A scheduler in many ways is an amped up priority queue.
ReplyDeleteFantastic work Asbjørn Heid. IMHO, you should replace built-in collections with Spring4D equivalents
ReplyDeleteSub
ReplyDeleteAsbjørn Heid great - thanks!
ReplyDeleteHow do you think the heap's performance compares with that of other sorted lists (e.g. skip lists, binary tree)?
Steve Maughan Good question, I planned on trying a skip list so I could compare. Of course the main drawback with a skip list is that it's worst case is O(n) but unless n is huge that shouldn't be a huge issue. Not sure if a balanced binary tree would be a big improvement, due to the amount of indirection which should hurt cache.
ReplyDelete