python3 queue.PriorityQueue changes?

Question

I am in the process of "porting" an application of mine from py27 to py33. For the most part it is quite trivial. That said I have a very odd difference between py27 & py33

I basically have two threads and they communicate via queues. The type of data being sent is such:

TX_Queue.put( (3,'SOME_TAG',{some:type,of:data} )

ie, priority, command, data

This works perfectly fine in py27, but now that most of the conversion to py33 is complete I am getting an odd exception every now and again:

return heappop(self.queue)
TypeError: unorderable types: dict() < dict()

Any idea's what this is or what changed between py27 and py3 with respect to PriorityQueues?

Answer 1

Nothing has changed related to PriorityQueues; what's changed is related to dict, and more generally to sorting objects that have no natural ordering.

The problem is that you're trying to sort two tuples that contain dicts, like this:

(3, 'SOME_TAG', {'some': 'type', 'of': 'data'})

Tuples compare lexicographically—that is, they first compare the first element, and if those are equal they then try the second element, and if those are equal they then try the third, and so on.

Most of the time, the first or second element will differ, so you won't ever need to compare the third elements, so everything will be fine.

But occasionally, you'll get two values like this:

(3, 'SOME_TAG', {'some': 'type', 'of': 'data'})
(3, 'SOME_TAG', {'some': 'othertype', 'with': 'differentdata'})

And then, it will need to compare the two dicts to decide which tuple is less.

This is a meaningless thing to do. Dictionaries' items are inherently unordered, so how can you decide which one is less than the other one? In fact, even if there were a fixed and predictable element to the items, what would be the rule you'd expect here? Is the first one less because 'of' < 'with'? Or greater because 'other type' < 'type'? Or…?

Python 2.x just does something arbitrary and useless; Python 3.x instead raises an exception. This is documented under Ordering Comparisons in the "What's New in 3.x" docs:

The ordering comparison operators (<, <=, >=, >) raise a TypeError exception when the operands don’t have a meaningful natural ordering.

So, you already had a problem in these cases, but Python 2.x hid the problem by occasionally silently doing something useless, while 3.x makes the problem obvious.

---

So, what's the solution? Well, what do you want to happen? My guess is that you actually want to sort the first element, ignoring the other elements. In that case, you were getting something close to that automatically in Python 2.x, and you probably didn't notice that sometimes it was unstable in unpredictable ways. But if you actually want that behavior, in both versions, you have to write it yourself.

Unfortunately, unlike most sort-related functions and objects in Python, PriorityQueue doesn't take a key function.* This means you have to "decorate-sort-undecorate" manually. But that isn't too hard. For example:

class TupleSortingOn0(tuple):
    def __lt__(self, rhs):
        return self[0] < rhs[0]
    def __gt__(self, rhs):
        return self[0] > rhs[0]
    def __le__(self, rhs):
        return self[0] <= rhs[0]
    def __ge__(self, rhs):
        return self[0] >= rhs[0]

Then you can do this:

TX_Queue.put(TupleSortingOn0(3,'SOME_TAG',{some:type,of:data}))

---

* Because it uses heapq under the covers, and heapq doesn't handle keys because the design of "functions that work on a normal list" precludes it…