Использование queue.PriorityQueue, не заботясь о сравнениях

Question

Я пытаюсь использовать 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__ и другие методы сравнения в моем пользовательском классе?Я нахожу это решение особенно уродливым и нелогичным, но это может быть я.

Answer 1

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

Answer 2

Давайте предположим, что мы не хотим писать декоратор с эквивалентной функциональностью для 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

Answer 3

Все, что вам нужно, это класс-оболочка, который реализует __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 (), эта реализация нестабильна.

Answer 4

См. примечания к реализации приоритетной очереди - непосредственно перед цитируемым разделом (касающимся использования dataclasses) в нем рассказывается, как это сделать без их:

... - для сохранения записей в виде списка из 3 элементов, включая приоритет, количество записей и задачу.Счетчик записей служит для разрешения конфликтов, поэтому две задачи с одинаковым приоритетом возвращаются в порядке их добавления.И поскольку нет двух одинаковых счетчиков записей, сравнение кортежей никогда не будет пытаться напрямую сравнить две задачи.

Поэтому просто добавьте свои элементы как 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): выдвигает триплеты как элементы, которые гарантированно имеют отличные 2-е значения, поэтому наши O() -инстанции никогда не используются в качестве прерывателя связей.

Вывод:

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

---

см. MartijnPieters ответ @ здесь длялучший уникальный 2-й элемент.