是否可以将比较器传递给 python 中的 PriorityQueue

Question

我想使用一个 PriorityQueue，我需要向其中添加我无法修改的 class（比如节点）的对象。我需要根据对象的字段对这些对象进行优先排序。

我尝试将它们作为元组（node.val，节点）添加到队列中。它仍然给我 "TypeError: '<' not supported between instances of 'Node' and 'Node'"。它仍然比较 'node' 对象来解决关系。

a = Node(3)
b = Node(4)

q = queue.PriorityQueue()
q.put(a)
q.put(b) // Errors TypeError: '<' not supported between instances of 'Node' and 'Node'

q.put((a.val, a))
q.put((b.val, b)) // Errors TypeError: '<' not supported between instances of 'Node' and 'Node'

我理解这个错误的原因是节点对象需要相互比较，根据文档实现这一点的方法是至少实现 lt 和 eq 节点的方法。 https://docs.python.org/3.1/library/stdtypes.html#comparisons.

但对于我的问题，由于我无法修改节点 class，我能否将一种方式（lambda 或比较器）传递给 PriorityQueue 以帮助它确定排序。（我期待 Java 之类的东西）

q = PriorityQueue(comparator)

也欢迎任何替代方法来实现这一点。（记住 Node 是不可修改的）

Answer 1

一种不通过比较器的解决方案是将您的 Node 对象包装在另一个对象中，比如 ComparableNode，它实现了您希望在 Node 对象上进行的比较。

假设您有此设置：

class Node:
    def __init__(self, val):
        self.val = val

    def __repr__(self):
        return "Node(val={})".format(self.val)


a = Node(3)
b = Node(4)
c = Node(4)

但是你不能修改Node。因此，您可以将其包装在您创建的 class 中。

@functools.total_ordering
class ComparableNode(Node):
    def __gt__(self, other):
        return self.val > other.val

    def __eq__(self, other):
        return self.val == other.val


aa = ComparableNode(3)
bb = ComparableNode(4)
cc = ComparableNode(4)

或者如果您只想传递 Node 个已经存在的对象：

@functools.total_ordering
class ComparableNode:
    def __init__(self, node):
        self.node = node

    def __gt__(self, other):
        return self.node.val > other.node.val

    def __eq__(self, other):
        return self.node.val == other.node.val

    def __repr__(self):
        return repr(self.node)


aa = ComparableNode(a)
bb = ComparableNode(b)
cc = ComparableNode(c)

然后正常添加即可：

p = PriorityQueue()
p.put(aa)
p.put(bb)
p.put(cc)

p.queue  # [Node(val=3), Node(val=4), Node(val=4)]

另一种方式，如果您可以在推入元素时指定每个元素的优先级。例如，这可以通过 heapq 实现。

与heapq：

import heapq

q = []
heapq.heappush(q, (a.val, a))
heapq.heappush(q, (b.val, b))

q  # [(3, Node(val=3)), (4, Node(val=4))]

对于 queue.PriorityQueue，使用 the doc

建议的元组

from queue import PriorityQueue

p = PriorityQueue()
p.put((a.val, a))
p.put((b.val, b))

p.queue  # [(3, Node(val=3)), (4, Node(val=4))]

如果您有重复值，则比较将查看元组的第二个元素，并且会中断，因为您的 Node 不可比较。在那种情况下，这取决于您要如何处理重复值。如果你想在重复的情况下保留插入顺序，你可以这样做：

from queue import PriorityQueue
from itertools import count

p = PriorityQueue()
index = count(0)

p.put((b.val, next(index), b))
p.put((c.val, next(index), c))

p.queue  # [(4, 0, Node(val=4)), (4, 1, Node(val=4))]

并以类似的方式处理 heapq。您可以轻松地将此行为包装在一个小函数中，这样您就可以减少自己的重复。

p = PriorityQueue()
index = count(0)

def put_priority(node):
    p.put((node.val, next(index), node))

Answer 2

PriorityQueue class 不允许 key 参数。虽然，您可以 subclass 它通过将每个项目隐式包装在比较对象中来实现，这里称为 _Wrapper.

from queue import PriorityQueue


class _Wrapper:
    def __init__(self, item, key):
        self.item = item
        self.key = key

    def __lt__(self, other):
        return self.key(self.item) < other.key(other.item)

    def __eq__(self, other):
        return self.key(self.item) == other.key(other.item)


class KeyPriorityQueue(PriorityQueue):
    def __init__(self, key):
        self.key = key
        super().__init__()

    def _get(self):
        wrapper = super()._get()
        return wrapper.item

    def _put(self, item):
        super()._put(_Wrapper(item, self.key))

用法

这是一个优先级队列的例子，它颠倒了顺序或元素。

key_pq = KeyPriorityQueue(key=lambda x: -x)

如果你需要一个比较器而不是一个键，你可以使用 functools.cmp_to_key 助手。

from functools import cmp_to_key

key_pq = KeyPriorityQueue(key=cmp_to_key(some_comparator))

是否可以将比较器传递给 python 中的 PriorityQueue

Is it possible to pass a comparator to a PriorityQueue in python

python

priority-queue

comparator

python-3.x

用法