Как изменить порядок PriorityQueue в python?

Я создал простую очередь приоритетов в python, которая упорядочивает элементы по их значению:

import Queue
q = Queue.PriorityQueue()
for it in items:
    q.put((it.value, it))

но когда я печатаю очередь, используя:

while not q.empty()
    print q.get()

он всегда будет сначала печатать наименьшее значение. есть ли способ получить последний элемент в очереди, не меняя последние две строки в верхнем бите кода на:

for it in items:
    q.put((-1*it.value, it))

потому что это кажется немного запутанным и создает проблемы, если я хочу использовать эту информацию для чего-то другого (мне придется снова умножить ее на -1)


python queue priority-queue
person guskenny83    schedule 25.03.2015    source источник

Ответы (7)


arrow_upward
3
arrow_downward

Вы можете просто создать свой собственный класс, который наследуется от PriorityQueue и выполняет за вас беспорядочное умножение на -1:

class ReversePriorityQueue(PriorityQueue):

def put(self, tup):
    newtup = tup[0] * -1, tup[1]
    PriorityQueue.put(self, newtup)

def get(self):
    tup = PriorityQueue.get(self)
    newtup = tup[0] * -1, tup[1]
    return newtup

Похоже, это работает с кортежами, по крайней мере:

Q = ReversePriorityQueue()

In [94]: Q.put((1,1))

In [95]: Q.get()
Out[95]: (1, 1)

In [96]: Q.put((1,1))

In [97]: Q.put((5,5))

In [98]: Q.put((9,9))

In [99]: Q.get()
Out[99]: (9, 9)

In [100]: Q.get()
Out[100]: (5, 5)

In [101]: Q.get()
Out[101]: (1, 1)

Я уверен, что вы могли бы обобщить код для работы не только с кортежами отсюда.

person James Kelleher    schedule 25.03.2015

arrow_upward
0
arrow_downward

Вы можете сделать трансформацию прозрачной.

Что вам нужно, так это иметь новый q.get и новый q.put, которые прозрачно изменяют данные в очереди и вне очереди в обратном порядке:

# new reversed priority put method
q.oldput = q.put
q.put = lambda p, i: q.oldput((p * -1, i))

# new reversed priority get method
q.oldget = q.get
# create get closure for queue
def newget(q):
    def g():
        item = q.oldget()
        # reverse first element
        return item[0] * -1, item[1]
    # return get method for given queue
    return g
# bind to queue
q.get = newget(q)

# test
items = range(10)
for it in items:
    q.put(*(it, it))

while not q.empty():
    print q.get()

Если это должно быть сделано для более надежного кода, я настоятельно рекомендую использовать класс, а не просто повторно связывать методы.

person Reut Sharabani    schedule 25.03.2015

arrow_upward
0
arrow_downward

Вы можете использовать настраиваемый класс вместо кортежа. Затем вы можете делать все, что вам нравится в cmp.

person Wei Qiu    schedule 02.01.2018

arrow_upward
0
arrow_downward

Если вы хотите избежать умножения на -1 при помещении в очередь приоритетов. Вы можете сделать что-то вроде этого.

Сделать класс-оболочку

class Wrapper:
    def __init__(self, value):
        self.value = value
    
    def __lt__(self, next):
        return self.value[0] > next.value[0]

Обратите внимание, что я изменил функцию __lt__, я намеренно использовал > вместо <.

Теперь, чтобы поместить элемент в очередь приоритетов, выполните

from queue import PriorityQueue
pq = PriorityQueue()
pq.put(Wrapper((priority, 'extra data')))

Теперь при получении элемента обязательно используйте вместо него атрибут value

t = pq.get().value
person Shahrukh Mohammad    schedule 02.09.2020

arrow_upward
-1
arrow_downward

По определению вы можете извлекать элементы только из начала очереди. Чтобы изменить порядок, вы можете поместить все в стек, а затем извлечь элементы из стека. Поскольку стек одновременно добавляет и извлекает элементы из своей задней части, это имеет тот же эффект, что и обращение очереди.

person Alecg_O    schedule 25.03.2015
comment
но это означало бы помещать все в стек каждый раз, когда я хотел получить что-то из конца очереди, не так ли? я думаю, это было бы очень неэффективно, особенно для очень больших размеров ввода. - person guskenny83; 25.03.2015

arrow_upward
-1
arrow_downward

В случае Queue.PriorityQueue

Сначала извлекаются записи с наименьшим значением (запись с наименьшим значением — это запись, возвращаемая sorted(list(entries))[0]).

Итак, вы можете попробовать queue.LifoQueue. Это механизм LIFO.

person itzMEonTV    schedule 25.03.2015

arrow_upward
-2
arrow_downward

Согласно spec (при условии, что Python 2.7):

The lowest valued entries are retrieved first

Так что это будет означать, нет, вы не можете.

person Gx1sptDTDa    schedule 25.03.2015
comment
Честно говоря, я прочитал спецификацию, но подумал, что может быть какой-то другой специальный метод, который я пропустил, или что-то в этом роде. неважно, я могу просто умножить на -1, я полагаю - person guskenny83; 25.03.2015