Поддерживать две очереди приоритетов объектов одного типа с разными атрибутами сортировки для каждого - PullRequest
Новая
       5

Поддерживать две очереди приоритетов объектов одного типа с разными атрибутами сортировки для каждого

0 голосов
/ 11 марта 2020

Итак, у меня есть класс P. Я хочу две приоритетные очереди объектов типа P, а также приоритетную очередь объектов типа P. Однако я хочу заказать один из них на P.x, а другой на P.y. Теперь queue.PriorityQueue.put() не поддерживает функцию клавиш, поэтому я прибегнул к следующим действиям: 

class P:
    ...
    def __lt__(self, other):
        return self.y < other.y
    ...

Однако это не позволяет выполнять сортировку на основе P.x, и в то же время я хотите просмотреть одну из очередей, но не другую, и queue.PriorityQueue не имеет функции peek. Поэтому я заменил одну из приоритетных очередей отсортированным списком. Я не могу использовать библиотеку SortedContainers, потому что она предназначена для домашнего задания, и я не могу гарантировать, что она установлена ​​на оценочном сервере, поэтому я перешел к использованию bisect.insort.

Единственная проблема однако bisect.insort также не поддерживает ключевые функции. Поэтому мне пришлось написать свою собственную функцию binary_insert(lst, item, key) для выполнения sh этой задачи, а затем я вызываю ее с помощью binary_insert(lst, item, key = lambda i: i.x). Это похоже на хак, так как я пишу свою собственную функцию двоичной вставки, а двоичная вставка является такой базовой концепцией компьютерной науки, что это должно было прийти раньше.

Один из способов сделать это - это иметь кортежи хранилища списка формы (x, p) и имеют кортежи хранилища очереди с приоритетами формы (y, p). Но есть ли другой способ включить эти атрибуты в P? В противном случае мне придется распаковывать кортеж каждый раз, когда я извлекаю элемент, и это может привести к тому, что моя программа будет завалена неиспользованными переменными.

1 Ответ

0 голосов
/ 11 марта 2020

Возможно, вы можете создать подкласс PriorityQueue, чтобы сделать кортежи для вас, что-то вроде этого (полностью непроверенный код): 

class MyPriorityQueue(PriorityQueue):
    def _put(self, item):
        super()._put((item.x, item))

    def _get(self):
        return super()._get()[1]
...