元组和字典的优先队列

Question

问题陈述

目前我正在用 Python 实现 A* 搜索算法（针对特定问题进行了大量修改）。作为问题的组成部分，我需要快速访问后进先出顺序中的最小启发式值。 Python 的优先级队列看起来最好。我的数据结构已经是具有父关系的字典列表，所以能够对它们进行排序会很好。但是，我似乎很难这样做。例如，我有一个新字典的例子：

 queue = PriorityQueue() # Could be instantiated based on an existing list of dicts
exampleDict = {"x": 10, "y": 20, "f": 123, "parent":{}}

我希望能够通过元组或类似形式将这本字典插入优先级队列

queue.put((exampleDict["f"], exampleDict))

请注意，我无法尝试使用外部库，因此我正在寻找更原生的 py3 解决方案。

发生了什么

我已经尝试了所有对我来说显而易见的解决方案。阅读文档，我发现 Python 允许一个元组，其中元组中的第二项是字典，第一项是优先级：

 parent = {'x': 0, 'y': 0, 'parent': False, 'f': 0, 'g': 50, 'wallPassed': 0}
something = (1, {'h': 9, 'x': 0, 'y': 1, 'parent': parent, 'f': 60, 'g': 51, 'wallPassed': 0})
somethingElse = (1, {'h': 9, 'x': 1, 'y': 0, 'parent': parent, 'f': 60, 'g': 51, 'wallPassed': 1})
test = PriorityQueue()
test.put(something)
test.put(somethingElse)

它在插入一个值时有效，但是在我插入另一个值的那一刻它失败了

Traceback (most recent call last):
  File "test.py", line 8, in <module>
    test.put(somethingElse)
  File "C:\Users\champloo11\AppData\Local\Programs\Python\Python35-32\lib\queue.py", line 143, in put
    self._put(item)
  File "C:\Users\champloo11\AppData\Local\Programs\Python\Python35-32\lib\queue.py", line 227, in _put
    heappush(self.queue, item)
TypeError: unorderable types: dict() < dict()

有什么可以做的吗？似乎没有太多关于问题的文档记录方式，或者在没有 frozendict 的情况下解决问题。

原文由 Daymon Schroeder 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

问题是字典在 Python 中是不可排序的类型。也就是说，如果您尝试运行以下内容：

 >>> {'alpha': 1} < {'beta': 2}
----> 1 {'alpha': 1} < {'beta': 2}

TypeError: unorderable types: dict() < dict()

你会得到一个 TypeError 。您尝试使用的技巧是将字典包装成一个元组，该元组的第一个元素 是 可排序的——类似于数字。然后我们可以比较它们：

 >>> (1, {'alpha': 1}) < (2, {'beta': 2})
True

现在看看 Python 如何比较元组是值得的。首先，Python 比较每个元组的第一个条目。在这种情况下， 1 < 2 ，Python 返回 True 。但是，如果第一个条目没有排序——假设它们相同——Python 就会去比较 第二个 条目。例如

>>> (1, 42) < (2, 7)
True
>>> (1, 42) < (1, 88)  # 42 < 88
True
>>> (1, 42) < (1, 7)   # 42 >= 7
False

所以在你上面的例子中发生的是你有两个元组具有相同的第一个条目，每个的第二个条目是一个字典。因此 Python 比较前两个条目，无法确定它们的顺序，然后尝试比较第二个条目，它们是字典并且无法排序。在一个例子中，

 >>> (1, {'alpha': 1}) < (2, {'beta': 2})
True

正如我们在上面看到的那样，工作得很好。但是更改右侧元组的第一个条目会出现错误：

 >>> (1, {'alpha': 1}) < (1, {'beta': 2})
----> 1 (1, {'alpha': 1}) < (1, {'beta': 2})
TypeError: unorderable types: dict() < dict()

---

那么什么是正确的解决方案呢？如果你有办法为每个字典分配一个 唯一的 优先级，那么元组方法就会起作用。但是每个元组的第一个条目必须是唯一的！否则 Python 将求助于比较第二个条目，它们是字典，您将再次遇到同样的问题。

如果这不可能或不可取，那么我们必须为 Python 提供一种比较这两个词典的方法。一种方法是创建一个 PriorityEntry 类并定义其 __lt__ 方法。要创建此类的实例，您需要提供可以排序的优先级和不需要排序的数据。然后 __lt__ 仅按优先级而非数据对类的两个实例进行排序。那是：

 class PriorityEntry(object):

    def __init__(self, priority, data):
        self.data = data
        self.priority = priority

    def __lt__(self, other):
        return self.priority < other.priority

所以

>>> PriorityEntry(1, {'alpha': 1}) < PriorityEntry(1, {'beta': 2})
False
>>> PriorityEntry(1, {'alpha': 1}) < PriorityEntry(2, {'beta': 2})
True

或者，使用您的数据：

 parent = {'x': 0, 'y': 0, 'parent': False, 'f': 0, 'g': 50, 'wallPassed': 0}
something = PriorityEntry(1, {'h': 9, 'x': 0, 'y': 1, 'parent': parent, 'f': 60, 'g': 51, 'wallPassed': 0})
somethingElse = PriorityEntry(1, {'h': 9, 'x': 1, 'y': 0, 'parent': parent, 'f': 60, 'g': 51, 'wallPassed': 1})
test = PriorityQueue()
test.put(something)
test.put(somethingElse)

现在将在不引发错误的情况下运行。

原文由 jme 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

优先级队列中不可排序数据的常见解决方案是向元组添加一个额外的值，该值在两个不同的条目中永远不会相等。它将打破具有相同优先级的两个项目之间的“联系”，而无需订购数据。稳定增加的整数是一种简单的方法：

 import heapq
import itertools

unorderable_data = {"foo": "bar"}

heap = []
counter = itertools.count()

entry1 = (2, next(counter), unorderable_data)
entry2 = (1, next(counter), unorderable_data)
entry3 = (2, next(counter), unorderable_data)

heapq.heappush(heap, entry1)
heapq.heappush(heap, entry2)
heapq.heappush(heap, entry3)

priority, tie_breaker, data = heapq.heappop(heap)

print(priority, data) # prints 1, {"foo": "bar"}

除了展示如何向元组添加决胜项之外，我还在此处演示了使用 heapq 模块在列表中实现优先级队列，而不是创建 queue.PriorityQueue 类。整个 queue 模块旨在使多线程程序中的序列化通信成为可能，因此它的类都会有一堆与锁相关的开销，如果您正在创建单线程应用程序，则不需要这些开销. PriorityQueue 类在幕后使用了 heapq 模块，我建议直接使用它。

原文由 Blckknght 发布，翻译遵循 CC BY-SA 3.0 许可协议