2

I'm designing (not writing, yet) a task scheduler system for a complex video game. The rest of the program passes it objects containing a function and some metadata including an estimation of how much time is left before the data is needed (which can change, of course). The scheduler is responsible for prioritizing these tasks and calling the function.

The algorithm I've designed for this problem is pretty simple; it just sorts its list of task objects, pops one off the top, calls it, and repeats. Of course it's actually more complex than that (has to handle situations where things just can't get done on time, telling other parts of the code that their task just got bumped down the list...), but that's the gist of it.

I'd like some advice on the subject of how I'm going to sort that list. This loop will, obviously, be running constantly while the program is running. I'm thinking I'll use a slight modification of a bubble sort algorithm, running one pass on each iteration. The list won't be properly sorted for the first few cycles, but since the list will likely be very small when the program is started I expect it will be able to reliably get things into position as fast as they come in.

Has anyone done this before, and how did it work? Are there better ways I could do this?

  • 3
    What you're looking for is a priority queue. Google will be abound with implementations and explanations of the high level approaches generally used in all sorts of contexts. – Servy Aug 22 '13 at 20:00
  • How about the insertion sort instead of the bubble sort: en.wikipedia.org/wiki/Insertion_sort – Lorenzo Baracchi Aug 22 '13 at 20:05
  • @Servy, you should make that an answer. – Karl Bielefeldt Aug 22 '13 at 20:09
6

You should be using a Priority Queue here. A Priority Queue is a queue in which items added to the queue have a priority, and whenever you get an item, you get the item with the minimum (or maximum, depending on implementation) priority.

Priority Queues are generally implemented using a min-heap (or max-heap). It will logically represent the data as a completely balanced tree in which each node is "less than" all of its children. It's not technically a binary search tree, in which the data is fully sorted. (Which is a viable alternative that is only slightly more expensive.) Since the data isn't actually completely sorted it means the only real meaningful operations you can perform are "Give me the lowest value" and "add this new value to the collection". (Incidentally, those are exactly the two operations that you need.) Both of which can be performed in O(log(n)) time. Because the min-heap ensures that the tree is always entirely balanced there is very little variance in the best/worst case. Even it's worst case is quite low, unlike a binary search tree which, if it gets unbalanced, can devolved into O(n) operatiosn.

|improve this answer|||||
  • Do you have a source for a clear explanation of how to implement that? – Schilcote Aug 22 '13 at 20:30
  • @Schilcote You can find lots of details about all of the concepts involved on Wikipedia; the pages for priority queues and the heap data structure all have lots of information. Beyond that, Google is filled with actual concrete implementations in all sorts of languages, and many will already have an implementation in their standard library. Ideally you wouldn't be writing one from scratch, but rather using your language's (or a 3rd parties, if needed) implementation. – Servy Aug 22 '13 at 20:32
  • Unless I misunderstand, that doesn't work in situations where priority is dynamic. – Schilcote Aug 22 '13 at 20:42
  • @Schilcote That's correct, but I fail to see how your case is dynamic. You can just have the key be the time that the data is needed, and you then minimize that, thus getting the item that is needed "next". If you have an implementation that can only take integer keys, rather than any comparable item, then simply convert the date/time into milliseconds since epoch or similar. – Servy Aug 22 '13 at 20:45
  • 1
    @Schilcote Then even sorting doesn't help you, because your sort is invalidated almost immediately. There isn't anything to do but store all of the object in any old unordered collection and do a linear search to find the min value each time you need it. (That linear search is still faster than sorting each time, especially considering you're using a very inefficient sorting algorithm.) – Servy Aug 22 '13 at 21:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.