python - 元组和字典的优先队列

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 就可以解决问题。

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)

现在将运行而不会引发错误。