如果项目不可比较，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'

official heapq document for python2 and python3 中提到了这一点，文档建议对 heapq 进行 DIY 实施以缓解此问题。

为什么会这样？鉴于 heapq 是一个非常古老的图书馆，这种冲突没有得到解决的根本原因是什么？这是否有性能/其他问题？为什么我们不能只提供像 keep_old, keep_any 这样的参数作为这个库的一个特性？

Answer 1

我的第一个想法是堆需要排序；由于您向堆中添加了两个 P0 项，并且当优先级相等时堆回退到对值进行排序，因此必须对值进行排序。如果这是你想要的，我会将 map 子类化为 comparableMap("k", {"k":0}) 并在其上添加一个比较方法。

Answer 2

来自 Priority Queue Implementation Notes 上的 heapq 文档部分：

A solution to the first two challenges is to store entries as 3-element list including the priority, an entry count, and the task. The entry count serves as a tie-breaker so that two tasks with the same priority are returned in the order they were added.

对此的简单解释：

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() 来完成此操作。）

给事物注入一点意见：

Why is this happening? What is the underlying reason that such conflict is not resolved, giving that heapq is a really old library?

不太确定，但事实是，您无法从逻辑上比较两个 dict 小于 than/greater。

独立于 heapq，比较 (0,{"k":0}) > (0,{"k":1}) 将（理所当然地）提出 TypeError。 heapq 的强调操作应该是 确定性的 ：tie-break 不应该是随机的，由您根据情况决定如何处理。

如果项目不可比较，heapq 无法处理具有相同优先级的元组

heapq can't handle tuples having same priority if the item is not comparable

python

heapq