2

我正在尝试queue.PriorityQueue在 Python 3(.6) 中使用。

我想存储具有给定优先级的对象。但是如果两个对象具有相同的优先级，我也不介意PriorityQueue.get返回。换句话说，我的对象不能以整数进行比较，允许它们进行比较是没有意义的，我只关心优先级。

在Python 3.7 的文档中，有一个解决方案涉及dataclasses. 我引用：

如果数据元素不可比较，则可以将数据包装在一个忽略数据项而只比较优先级编号的类中：

from dataclasses import dataclass, field
from typing import Any

@dataclass(order=True)
class PrioritizedItem:
    priority: int
    item: Any=field(compare=False)

唉，我正在使用 Python 3.6。在这个版本的 Python 的文档中，没有关于使用PriorityQueue优先级的评论，而不是关心在我的情况下不合逻辑的“对象值”。

有没有比__le__在我的自定义类上定义和其他比较方法更好的方法？我发现这个解决方案特别丑陋和违反直觉，但那可能是我。

4

4 回答 4

5

dataclasses只是一种避免创建大量样板代码的便捷方法。

您实际上不必创建一个类。一个具有唯一计数器值的元组：

from itertools import count

unique = count()

q.put((priority, next(unique), item))

这样相同优先级之间的关系就会被后面的整数打破；因为它始终是唯一的，item所以永远不会咨询该值。

您还可以使用直接丰富的比较方法创建一个类，使用以下方法变得更简单@functools.total_ordering：

from functools import total_ordering

@total_ordering
class PrioritizedItem:
    def __init__(self, priority, item):
        self.priority = priority
        self.item = item

    def __eq__(self, other):
        if not isinstance(other, __class__):
            return NotImplemented
        return self.priority == other.priority

    def __lt__(self, other):
        if not isinstance(other, __class__):
            return NotImplemented
        return self.priority < other.priority
于 2019-01-03T19:09:40.967 回答
2

请参阅优先级队列实现说明-就在您引用的部分之前（关于 using ）dataclasses它告诉您如何在没有它们的情况下执行此操作：

... 是将条目存储为 3 元素列表，包括优先级、条目计数和任务。条目计数用作决胜局，以便具有相同优先级的两个任务按照它们添加的顺序返回。并且由于没有两个条目计数相同，元组比较永远不会尝试直接比较两个任务。

因此，在添加到队列时，只需将您的项目添加为元组中的第三个元素。(Prio, Count, YourElem)

拟定示例：

from queue import PriorityQueue

class CompareError(ValueError): pass

class O:
    def __init__(self,n):
        self.n = n

    def __lq__(self):
        raise CompareError

    def __repr__(self): return str(self)
    def __str__(self): return self.n

def add(prioqueue,prio,item):
    """Adds the 'item' with 'prio' to the 'priorqueue' adding a unique value that
    is stored as member of this method 'add.n' which is incremented on each usage."""
    prioqueue.put( (prio, add.n, item))
    add.n += 1

# no len() on PrioQueue - we ensure our unique integer via method-param
# if you forget to declare this, you get an AttributeError
add.n = 0

h = PriorityQueue()

add(h, 7, O('release product'))
add(h, 1, O('write spec 3'))
add(h, 1, O('write spec 2'))
add(h, 1, O('write spec 1'))
add(h, 3, O('create tests'))

for _ in range(4):
    item = h.get()
    print(item)

使用h.put( (1, O('write spec 1')) ) 导致

TypeError: '<' not supported between instances of 'O' and 'int'`

使用def add(prioqueue,prio,item):pushs 三元组作为保证不同的第二个值的项目，因此我们的O()-instances 永远不会用作决胜局。

输出：

(1, 2, write spec 3)
(1, 3, write spec 2)
(1, 4, write spec 1)
(3, 5, create tests)

请参阅MartijnPieters回答@here以获得更好的独特第二元素。

于 2019-01-03T18:45:32.017 回答
0

假设我们不想编写与dataclass. 问题是我们不想定义所有的比较操作符来使我们的自定义类基于优先级进行比较。装饰师可以提供@functools.total_ordering帮助。摘抄：

给定一个定义一个或多个丰富的比较排序方法的类，这个类装饰器提供其余的。这简化了指定所有可能的丰富比较操作所涉及的工作：

该类必须定义__lt__()、__le__()、__gt__()或之一__ge__()。此外，该类应该提供一个__eq__()方法。

使用提供的示例：

from functools import total_ordering

@total_ordering
class PrioritizedItem:
    # ...

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

    def __lt__(self, other):
        return self.priority < other.priority
于 2019-01-03T18:49:10.710 回答
0

__lt__您所需要的只是一个实现以便PriorityQueue正常工作的包装类。此处指出：

__lt__()在两个对象之间进行比较时，保证使用排序例程。所以，很容易通过定义一个__lt__()方法给一个类添加一个标准的排序顺序

就像这样简单

class PriorityElem:
    def __init__(self, elem_to_wrap):
        self.wrapped_elem = elem_to_wrap

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

如果您的元素没有优先级，那么它很简单：

class PriorityElem:
    def __init__(self, elem_to_wrap, priority):
        self.wrapped_elem = elem_to_wrap
        self.priority = other.priority

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

现在你可以PriorityQueue像这样使用

queue = PriorityQueue()
queue.put(PriorityElem(my_custom_class1, 10))
queue.put(PriorityElem(my_custom_class2, 10))
queue.put(PriorityElem(my_custom_class3, 30))

first_returned_elem = queue.get()
# first_returned_elem is PriorityElem(my_custom_class1, 10)
second_returned_elem = queue.get()
# second_returned_elem is PriorityElem(my_custom_class2, 10)
third_returned_elem = queue.get()
# third_returned_elem is PriorityElem(my_custom_class3, 30)

在这种情况下，获取您的原始元素将非常简单

elem = queue.get().wrapped_elem

由于您不关心排序稳定性，这就是您所需要的。

编辑：如评论中所述并在此处确认，heappush不稳定：

与 sorted() 不同，此实现不稳定。

于 2019-01-03T18:55:25.777 回答