Issue 17794: Add a key parameter to PriorityQueue (original) (raw)

Created on 2013-04-19 00:37 by Claymore, last changed 2022-04-11 14:57 by admin. This issue is now closed.

Messages (11)

msg187321 - (view)

Author: Carlos Ferreira (Claymore)

Date: 2013-04-19 00:37

I'm using Priority Queues and followed the Python documentation for a simple example.

From Queue documentation in Python 3.3 http://docs.python.org/3.3/library/queue.html " The lowest valued entries are retrieved first (the lowest valued entry is the one returned by sorted(list(entries))[0]). A typical pattern for entries is a tuple in the form: (priority_number, data). "

Then I tried this simple code.

pq = PriorityQueue() pq.put_nowait((0, {'a':1})) pq.put_nowait((0, {'a':2})) Traceback (most recent call last): File "", line 1, in File "/usr/lib/python3.3/queue.py", line 187, in put_nowait return self.put(item, block=False) File "/usr/lib/python3.3/queue.py", line 146, in put self._put(item) File "/usr/lib/python3.3/queue.py", line 230, in _put heappush(self.queue, item) TypeError: unorderable types: dict() < dict()

Is this a normal behaviour? I'm not sure if this should be declared as a bug...

Instead of sticking to the first argument that indicates the priority, the heapq algorithm checks the second field and tries to order the dictionaries.

I solved this annoyance by adding a third field, the object ID. Since the object ID is actually its address in memory, every object will have a different ID. Also, since the queue entries will have the same priority (zero), the id value is used to order the tuples in the heap queue.

pq = PriorityQueue() a = {'a':1} b = {'a':2} pq.put_nowait((0, id(a), a)) pq.put_nowait((0, id(b), b))

msg187324 - (view)

Author: R. David Murray (r.david.murray) * (Python committer)

Date: 2013-04-19 00:49

It is a bug of some sort. A doc bug if nothing else. This is probably due to the fact that everything was sortable in python2, and the doc and/or code hasn't been updated to account for the fact that many things aren't in Python3.

msg187757 - (view)

Author: Daniel Wong (allyourcode) *

Date: 2013-04-25 05:48

from the peanut gallery:

This looks right to me; you are seeing that PriorityQueue is trying to compare dicts, because that's how tuple comparison works: it is lexicographic. Since the first element of the two tuples that you are trying to insert have the same value, comparison of the two tuple reduces to comparing the second elements.

Your work around also looks good to me.

msg187807 - (view)

Author: Mark Dickinson (mark.dickinson) * (Python committer)

Date: 2013-04-25 19:09

Hmm. It's true that Python 3's comparison rules make PriorityQueue a bit less useful in its current form.

One possible workaround could be to introduce an optional "key" argument to the constructor that provides a callable used to map objects added to the queue to their priorities. The default key would map each object to itself, as before, but for a use-case like this one the key could just be lambda x: x[0].

msg187812 - (view)

Author: Mark Dickinson (mark.dickinson) * (Python committer)

Date: 2013-04-25 19:57

Example patch. Items with equal priority are retrieved in LIFO order.

msg187813 - (view)

Author: Mark Dickinson (mark.dickinson) * (Python committer)

Date: 2013-04-25 20:02

Hmm. This looks like a duplicate of #7174.

msg187814 - (view)

Author: Mark Dickinson (mark.dickinson) * (Python committer)

Date: 2013-04-25 20:10

Fixed patch.