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

摘自 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() 来执行此操作。)

<小时/>

向事物注入(inject)一些观点:

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

不太确定，但事实是你无法在逻辑上比较两个dict小于/大于。

独立于 heapq，比较 (0,{"k":0}) > (0,{"k":1}) 将(理所当然)引发TypeError。heapq的一个重点是操作应该是确定性:决胜局不应该是随机的，由您根据具体情况决定如何处理。