classification
Title: Add a key parameter to PriorityQueue
Type: enhancement Stage: resolved
Components: Library (Lib) Versions: Python 3.4
process
Status: closed Resolution: out of date
Dependencies: Superseder:
Assigned To: rhettinger Nosy List: Claymore, allyourcode, eric.snow, r.david.murray, rhettinger, serhiy.storchaka
Priority: normal Keywords: patch

Created on 2013-04-19 00:37 by Claymore, last changed 2019-08-24 00:25 by rhettinger. 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 "<stdin>", line 1, in <module>
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.
msg187828 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2013-04-26 05:48
I'm working on this one.  Expect a patch shortly.
msg187889 - (view) Author: Daniel Wong (allyourcode) * Date: 2013-04-27 05:38
btw, I have a related patch: http://bugs.python.org/issue17834 Chances of it being accepted aren't looking good right now though.
msg187893 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2013-04-27 08:20
Related issues: issue4356, issue13742.

See also issue1185383, issue1904 and issue1162363.
msg350340 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2019-08-24 00:25
Starting in Python 3.7, dataclasses made it trivially easy to work around this issue.  The PriorityQueue docs have a worked out example of how to do this: https://docs.python.org/3/library/queue.html#queue.PriorityQueue
History
Date User Action Args
2019-08-24 00:25:31rhettingersetstatus: open -> closed
resolution: out of date
messages: + msg350340

stage: resolved
2014-05-12 17:58:31eric.snowsetnosy: + eric.snow
2013-04-27 08:20:52serhiy.storchakasetnosy: + serhiy.storchaka
title: Priority Queue -> Add a key parameter to PriorityQueue
messages: + msg187893

versions: - Python 3.3
type: behavior -> enhancement
2013-04-27 05:38:02allyourcodesetmessages: + msg187889
2013-04-26 07:13:44mark.dickinsonsetnosy: - mark.dickinson
2013-04-26 07:13:28mark.dickinsonsetfiles: - issue17794.patch
2013-04-26 05:48:59rhettingersetassignee: rhettinger
messages: + msg187828
2013-04-25 20:11:13mark.dickinsonsetfiles: - issue17794.patch
2013-04-25 20:10:59mark.dickinsonsetfiles: + issue17794.patch

messages: + msg187814
2013-04-25 20:02:01mark.dickinsonsetmessages: + msg187813
2013-04-25 19:58:44mark.dickinsonsetfiles: - issue17794.patch
2013-04-25 19:58:33mark.dickinsonsetfiles: + issue17794.patch
2013-04-25 19:57:27mark.dickinsonsetfiles: + issue17794.patch
keywords: + patch
messages: + msg187812
2013-04-25 19:09:34mark.dickinsonsetnosy: + mark.dickinson
messages: + msg187807
2013-04-25 05:48:55allyourcodesetnosy: + allyourcode
messages: + msg187757
components: + Library (Lib), - Interpreter Core
2013-04-19 00:49:23r.david.murraysetnosy: + rhettinger, r.david.murray

messages: + msg187324
versions: + Python 3.4
2013-04-19 00:37:22Claymorecreate