时间戳

首页 > 解决方案 > 如果项目不可比较，heapq 无法处理具有相同优先级的元组

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

问题描述

>>> 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作为这个库的特性？

标签： pythonheapq

解决方案

来自优先队列实施说明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是操作应该是确定性的：抢七不应该是随机的，由你来决定如何处理它。

推荐阅读