![]() ![]() Tuples are ordered lexicographically, so (a, b) is smaller than (c, d) if a is smaller than c or if they're equal and b is smaller than d. That's why, when you want to prioritize tasks not just by their natural order (e.g., the string 'job1' being smaller than the string 'job2'), you use a tuple of priority and task. For its prioritization it just asks the whole item whether it's smaller than another. So you could also give it task strings alone, without extra priorities. Only we the users think of the pair as priority and task. It just thinks of the pair as one "item" and it never even looks into it. It doesn't think of the two values as priority and task. Note that you give Python's priority queue pairs of priority and task, but the queue doesn't care. Fortunately it's as simple as storing entries "as 3-element list including the priority, an entry count, and the task". If you want stability, you'll need to enforce it yourself. That's also why heapsort "is not a stable sort". And heaps don't naturally offer stability. ![]() As the documentation says, it's "using the heapq module". Priority queues "are often implemented with heaps" and Python is no exception. The expected result: QUIT goes out first, and then the rest, FIFO ordered: Build, Clean, Create, Build, Clean: > q.get() Now I'll dequeue the elements one by one. Return cmp(self.priority, other.priority) Self.priority = 0 if self.type_ = 'QUIT' else 1 I was asked to add an example that shows that q.get() actually mess things up with the FIFO ordering, so here's an elaborate example: class Job(object): What's the reason? how to overcome (keep the order of same prio elements)? For some reason this is not the case: > from Queue import PriorityQueueĪs can be seen from the example, the order has been mixed after one get(). Prio_queue.put((1, time.I'm using python's Queue.PriorityQueue, and ran into the following problem: when inserting several elements to the queue which have the same priority, I would expect the queue to serve them in the order of insertion (FIFO). Prio_queue.put((1, time.time(), 'This thing would come after Some Thing if we sorted by this text entry')) Prio_queue.put((2, time.time(), 'super blah')) Hopefully this helps as another example of how you might get the ordering you're after. ![]() I added a short sleep so this simple example works out in a reasonable way. I say fake because it's only approximately FIFO as entries that are added very close in time to one another may not come out exactly FIFO. Here's what it looks like if you use a timestamp to fake FIFO as a secondary priority using a date. Output 1.3 - This thing would come after Some Thing if we didn't add a secondary priority Prio_queue.put((1, 3, 'This thing would come after Some Thing if we sorted by this text entry')) Using a datetime value in the second position is a pretty trivial change, but feel free to poke me in comments if you're not able to get it working. Here's some example code with just a secondary numeric priority. A date/time priority would give you a priority queue that falls back to a FIFIO queue when you have multiple items with the same priority. Just use the second item of the tuple as a secondary priority if a alphanumeric sort on your string data isn't appropriate. ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |