heapq не может обрабатывать кортежи с одинаковым приоритетом, если элемент не сопоставим

Question

>>> from heapq import heappush
>>> heap = []
>>> heappush(heap,(0,{"k":0}))
>>> heappush(heap,(0,{"k":1}))
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: '<' not supported between instances of 'dict' and 'dict'

Это упомянуто в официальном документе heapq для python2 и python3 , и в документе предлагается самостоятельная реализация heapq для смягчения этой проблемы.

Почему это происходит? Какова основная причина того, что такой конфликт не разрешен, учитывая, что heapq действительно старая библиотека? Есть ли какие-то проблемы с производительностью / другими проблемами? Почему мы не можем просто предоставить такие параметры, как keep_old, keep_any, как функцию для этой библиотеки?

Answer 1

Из раздела heapq документов на Замечания по реализации очереди с приоритетом :

Решением первых двух проблем является сохранение записей в виде трехэлементного списка, включающего приоритет, счетчик записей и задачу. Счетчик записей служит в качестве прерывателя связей, поэтому две задачи с тем же приоритетом возвращаются в порядке их добавления.

Баскетбольная интерпретация этого:

from heapq import heappush
ecount = 0
heap = []

for priority, task in (
    (0, {"k":0}),
    (0, {"k":0}),
):
    heappush(heap, (priority, ecount, task))
    ecount += 1

Результат:

>>> heap
[(0, 0, {'k': 0}), (0, 1, {'k': 0})]

(Вы также можете сделать это с помощью enumerate().)

---

Чтобы добавить немного мнений в вещи:

Почему это происходит? Какова основная причина того, что такой конфликт не разрешен, учитывая, что heapq - действительно старая библиотека?

Не совсем уверен, но в том-то и дело, что вы не можете логически сравнить два dict меньше / больше чем.

Независимо от heapq, сравнение (0,{"k":0}) > (0,{"k":1}) будет (справедливо) повышаться TypeError. Акцент heapq состоит в том, что операции должны быть детерминированными : тай-брейк не должен быть случайным, и вам решать, как с этим справиться.

Answer 2

Моя первая мысль, что кучи должны быть заказаны; так как вы добавили два элемента P0 в кучу, и куча возвращается к упорядочению значения, когда приоритеты равны, значения должны быть упорядочены. если это то, что вы хотите, я бы подкласса сопоставил как сопоставимыйMap ("k", {"k": 0}) и добавил метод сравнения на этом.