classification
Title: PriorityQueue.put() fails with TypeError if priority_number in tuples of (priority_number, data) are the same.
Type: enhancement Stage:
Components: Library (Lib) Versions: Python 3.7
process
Status: open Resolution:
Dependencies: Superseder:
Assigned To: rhettinger Nosy List: Mikołaj Babiak, rhettinger
Priority: normal Keywords:

Created on 2017-08-08 14:09 by Mikołaj Babiak, last changed 2017-08-08 14:51 by rhettinger.

Messages (2)
msg299922 - (view) Author: Mikołaj Babiak (Mikołaj Babiak) Date: 2017-08-08 14:09
# list of tuples in form of (priority_number, data)
bugged = [
(-25.691, {'feedback': 13, 'sentiment': 0.309, 'support_ticket': 5}), (-25.691, {'feedback': 11, 'sentiment': 0.309, 'support_ticket': 3}), (-25.0, {'feedback': 23, 'sentiment': 0.0, 'support_ticket': 15}),
]

from queue import PriorityQueue

pq = PriorityQueue()

for item in bugged:
   pq.put(item)

# TypeError: '<' not supported between instances of 'dict' and 'dict'

It seems that if priority_numbers are equal, heapq.heapify() falls back to comparing data element from tuple (priority_number, data).
I belive this is an undesired behaviour.
It is acctually listed as one of implementation challenges on https://docs.python.org/3/library/heapq.html:
"Tuple comparison breaks for (priority, task) pairs if the priorities are equal and the tasks do not have a default comparison order."

In python 2.7 the issue in not present and PriorityQueue.put() works as expected
msg299929 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2017-08-08 14:51
I don't see any way to change PriorityQueue to fix this.  The non-comparability of dicts likely won't be restored, nor will the lexicographic comparison order of tuples be likely to change.

One possible way forward is to provide a wrapper with the desired comparison behavior:

    pq = PriorityQueue()
    pq.put(Prioritize(13, task))
    task = pq.get().item
  
where Prioritize is implemented something like this:

import functools

@functools.total_ordering
class Prioritize:

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

    def __eq__(self, other):
        return self.priority == other.priority

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

from queue import PriorityQueue, Empty
from contextlib import suppress

bugged = [
(-25.691, {'feedback': 13, 'sentiment': 0.309, 'support_ticket': 5}), (-25.691, {'feedback': 11, 'sentiment': 0.309, 'support_ticket': 3}), (-25.0, {'feedback': 23, 'sentiment': 0.0, 'support_ticket': 15}),
]

pq = PriorityQueue()

for priority, item in bugged:
    pq.put(Prioritize(priority, item))
with suppress(Empty):
    while True:
        item = pq.get_nowait().item
        print(item)
History
Date User Action Args
2017-08-08 14:51:06rhettingersetversions: + Python 3.7, - Python 3.6
nosy: + rhettinger

messages: + msg299929

assignee: rhettinger
type: behavior -> enhancement
2017-08-08 14:09:13Mikołaj Babiakcreate