What data structure would be the most efficient for a task scheduler?

Question

So in a game with various objects that perform various tasks, a naive approach would simply be to update the state of all of the existing items in the world every game update. This is what Minecraft does to handle furnaces, and similar items. A more efficient approach would be to schedule a task in the future, for example, when the next item will be smelted. Then only the current events need to be processed rather than all of them every update.

An implementation of this would be to have a sorted list, and every update, the start of the list is iterated and the items processed until a list item is reached that is scheduled to occur in a future update.

But what data structure would be most suitable?

• If I use a straight array, then only one allocation is used, but every time an element is inserted or removed, that will incur a shift of the remaining elements. O(n) complexity. The correct insertion point for an event scheduled to occur at an arbitrary time could be found via binary search with O(log n) complexity.
• If I use a linked list, then deleting the first few elements scheduled to occur in the current update would not entail traversing the entire list. But scheduling a new event would entail doing so, in order to find the correct insertion point.

What data structure would be most suitable for a constantly changing, ordered set like a scheduled events list? So far my only options have linear complexity for insertion and/or deletion. Is there an even better data structure that will have logarithmic or constant time complexity for that?

Answer 1

Two options you could consider:

• Ring buffer - this just an array with an index to the first/last element, wrapping around from the end of the array to the start using modular arithmetic. When you want to extract the first element, you increment the "first" index instead of shifting all the items down, making it O(1) to extract. It's is still O(n) to insert, though for this use case it sounds like you'd typically be inserting closer to the end than the start, since a newly scheduled task will often take as long to finish as anything that was scheduled earlier. This is especially true if you use multiple queues, one for short tasks and one for long tasks, so you don't have lots of short tasks jumping in line in front of long tasks and forcing them to move down.

• Min Heap - this is a binary tree where each child's key (completion time) is greater than or equal to its parent's. That makes it O(log n) both to insert an entry or extract the entry with the minimum key (earliest completion time)

Myself, I'd start with the ring buffer, since it's simpler code with less branching and more linear memory access, making it more cache-friendly. I'd expect that to outpace the heap up to values of n in the thousands, especially if your task durations are large relative to the time between additions to the queue (minimizing shifting work).

Answer 2

My recommendation would be to start with the simplest possible data structure, and hide it behind an interface that lets you replace the implementation later if you run into problems. Focus on what operations you need to do, and only implement those that you need.

Having said that, a Priority Queue sounds like it should serve your needs - it lets you add things in any order, and efficiently retrieve them in sorted order.