Daymon Schroeder Daymon Schroeder - 1 month ago 26
Python Question

Priority Queue with Tuples and Dicts

Problem Statement

Currently I am implementing an A* search algorithm (heavily modified for a particular problem) in Python. As a component of the problem, I need a fast access to the smallest heuristic value in LIFO order. Python's priority queue looked best. My data structure was already a list of dictionaries with parent relations, so it'd be nice to be able to sort those. However, I seem to be having difficulties doing so. For example, I have an example newly dictionary:

queue = PriorityQueue() # Could be instantiated based on an existing list of dicts
exampleDict = {"x": 10, "y": 20, "f": 123, "parent":{}}


I would like to be able to insert this dictionary into the priority queue via a tuple or some like-form

queue.put((exampleDict["f"], exampleDict))


Please note that I cannot try an external library, so I'm looking for a more native-to-py3 solution.

Whats Happening

I've tried every solution that was obvious to me. Reading the docs, I found that Python allows a tuple in which the second item in the tuple was the dictionary, and the first was the priority:

parent = {'x': 0, 'y': 0, 'parent': False, 'f': 0, 'g': 50, 'wallPassed': 0}
something = (1, {'h': 9, 'x': 0, 'y': 1, 'parent': parent, 'f': 60, 'g': 51, 'wallPassed': 0})
somethingElse = (1, {'h': 9, 'x': 1, 'y': 0, 'parent': parent, 'f': 60, 'g': 51, 'wallPassed': 1})
test = PriorityQueue()
test.put(something)
test.put(somethingElse)


It works when inserting one value, but the minute I insert another it fails

Traceback (most recent call last):
File "test.py", line 8, in <module>
test.put(somethingElse)
File "C:\Users\champloo11\AppData\Local\Programs\Python\Python35-32\lib\queue.py", line 143, in put
self._put(item)
File "C:\Users\champloo11\AppData\Local\Programs\Python\Python35-32\lib\queue.py", line 227, in _put
heappush(self.queue, item)
TypeError: unorderable types: dict() < dict()


Is there anything that can be done about this? There doesn't seem to bemuch in the way of documentation regarding the problem, or solving it without frozendict.

jme jme
Answer

The problem is that dictionaries are unorderable types in Python. That is, if you try to run something like:

>>> {'alpha': 1} < {'beta': 2}
----> 1 {'alpha': 1} < {'beta': 2}

TypeError: unorderable types: dict() < dict()

you'll get a TypeError. The trick you're trying to employ is to wrap the dictionary up into a tuple whose first element is orderable -- something like a number. Then we can compare them:

>>> (1, {'alpha': 1}) < (2, {'beta': 2})
True

Now it pays to look at how Python compares tuples. First, Python compares the first entries of each tuple. In this case, 1 < 2, and Python returns True. But if the first entries are not ordered -- say they are the same -- Python then goes to comparing the second entries. For instance

>>> (1, 42) < (2, 7)
True
>>> (1, 42) < (1, 88)  # 42 < 88
True
>>> (1, 42) < (1, 7)   # 42 >= 7
False

So what happens in your example above is that you have two tuples with the same first entry, and the second entry of each is a dictionary. Hence Python compares the first two entries, can't determine an order from them, and then attempts to compare the second entries, which are dictionaries and can't be ordered. In an example,

>>> (1, {'alpha': 1}) < (2, {'beta': 2})
True

works just fine, as we saw above. But changing the first entry of the tuple on the right gives an error:

>>> (1, {'alpha': 1}) < (1, {'beta': 2})
----> 1 (1, {'alpha': 1}) < (1, {'beta': 2})
TypeError: unorderable types: dict() < dict()

So what is the right solution? If you have a way of assigning a unique priority to each dictionary, then the tuple approach will work. But the first entry of each tuple must be unique! Otherwise Python will resort to comparing the second entries, which are dictionaries, and you'll have the same issue again.

If that isn't possible or desirable, then we have to give Python a way of comparing these two dictionaries. One way of doing this is to create a PriorityEntry class and define its __lt__ method. To create an instance of this class, you give a priority, which can be ordered, and data, which need not be orderable. Then __lt__ orders two instances of the class by their priorities only, and not by their data. That is:

class PriorityEntry(object):

    def __init__(self, priority, data):
        self.data = data
        self.priority = priority

    def __lt__(self, other):
        return self.priority < other.priority

and so

>>> PriorityEntry(1, {'alpha': 1}) < PriorityEntry(1, {'beta': 2})
False
>>> PriorityEntry(1, {'alpha': 1}) < PriorityEntry(2, {'beta': 2})
True

or, using your data:

parent = {'x': 0, 'y': 0, 'parent': False, 'f': 0, 'g': 50, 'wallPassed': 0}
something = PriorityEntry(1, {'h': 9, 'x': 0, 'y': 1, 'parent': parent, 'f': 60, 'g': 51, 'wallPassed': 0})
somethingElse = PriorityEntry(1, {'h': 9, 'x': 1, 'y': 0, 'parent': parent, 'f': 60, 'g': 51, 'wallPassed': 1})
test = PriorityQueue()
test.put(something)
test.put(somethingElse)

which will now run without raising the error.

Comments