1 
>>> 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'

这在python2和 python3的官方 heapq 文档中有所提及，该文档建议使用 DIY 实现heapq来缓解此问题。

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

4

2 回答 2

3

来自优先队列实施说明heapq的文档部分：

前两个挑战的解决方案是将条目存储为 3 元素列表，包括优先级、条目计数和任务。条目计数用作决胜局，以便具有相同优先级的两个任务按照它们添加的顺序返回。

对此的简单解释：

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是操作应该是确定性的：抢七不应该是随机的，由你来决定如何处理它。

于 2019-07-11T23:18:29.023 回答
1

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

于 2019-07-11T23:12:11.157 回答