[Python] When the priority is the same in Priority Queue, it can be acquired in the order in which it was added to the queue.

Introduction

Various queue classes are defined in the queue module of Python's built-in. There is a priority queue (Priority Queue) in it.

If the priorities are the same, it seems that you can get the items in the order they were added to the queue, but they are not. It is common to use the heap queue in Priority Queue. It is also implemented in Python using the heap queue (heapq). This is because the heap queue implementation shifts the order when popping from the queue (detailed explanation is omitted, but I will write it if requested). (For a detailed explanation of the heap itself, see the here site.) The source I tried is below.

from dataclasses import dataclass, field
from typing import Any
import queue


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

def main():
    #Prepare a queue
    priority_queue = queue.PriorityQueue()
    for index in range(15):
        priority = index % 3
        queue_item = QueueItem(priority=priority, item=index)
        priority_queue.put(queue_item)
        print(f"[input] priority:{priority} value:{index}")

    #take out
    while not priority_queue.empty():
        queue_item = priority_queue.get()
        priority = queue_item.priority
        value = queue_item.item
        print(f"[output] priority:{priority} value:{value}")

if __name__ == "__main__":
    main()

[input] priority:0 value:0 [input] priority:1 value:1 [input] priority:2 value:2 [input] priority:0 value:3 [input] priority:1 value:4 [input] priority:2 value:5 [input] priority:0 value:6 [input] priority:1 value:7 [input] priority:2 value:8 [input] priority:0 value:9 [input] priority:1 value:10 [input] priority:2 value:11 [input] priority:0 value:12 [input] priority:1 value:13 [input] priority:2 value:14 [output] priority:0 value:0 [output] priority:0 value:6 [output] priority:0 value:12 [output] priority:0 value:3 [output] priority:0 value:9 [output] priority:1 value:13 [output] priority:1 value:10 [output] priority:1 value:4 [output] priority:1 value:1 [output] priority:1 value:7 [output] priority:2 value:2 [output] priority:2 value:5 [output] priority:2 value:14 [output] priority:2 value:11 [output] priority:2 value:8

You can see that items with the same priority are not taken in the order in which they were added. Of course, if the priority is the same, it can be taken from anywhere, so the operation is correct. However, there was a case where I wanted to get items in the order in which they were added when the priorities were the same, so I implemented it.

approach

It is troublesome to implement the heap queue by yourself, so we will take a simple method. In Priority Queue in Python, if items added to the queue can be compared as numerical values, the lower the numerical value, the higher the priority. (If you cannot compare numerical values, use dataclasses as described above ... Reference) Taking advantage of this property, in addition to the priority of int, the time added to the queue is also retained in the queue item for comparison. By doing so, you can get the items in the order they were added to the queue.

It also implements getting the maximum priority and simplifying push-pop.

Implementation

Define the queue item and queue class as follows.

import time
from typing import Any, Tuple, Optional
from dataclasses import dataclass, field, asdict
import queue


@dataclass(order=True)
class QueueItem:
    """
Queue item
    """
    priority: int
    item: Any = field(compare=False)
    occurred: float = field(default=0.0, compare=True)


class PriorityQueue(queue.PriorityQueue):
    """
Priority queue class with time added
    """

    def __init__(self, priority_name: str = "priority"):
        """
        Args:
            priority_name:Priority variable name
        """
        self.priority_name: str = priority_name
        super().__init__()

    @property
    def max_priority(self, priority_name: Optional[str] = None) -> int:
        """
Get the highest priority
        """
        if not self.queue:
            return 0
        priority_name = priority_name or self.priority_name
        assert hasattr(self.queue[0], priority_name)

        max_priority = max([queue_item.priority for queue_item in self.queue])
        return max_priority

    def put_item(self, **kwargs):
        """
        put override
        """
        #I want to prioritize in the order of priority + registration
        if kwargs.get("occurred", None) is None:
            kwargs["occurred"] = time.perf_counter()

        #Item creation / addition
        queue_item = QueueItem(**kwargs)
        super().put(queue_item)

    def get_item(self) -> Tuple[Any, ...]:
        """
        get override
        """
        queue_item: QueueItem = super().get()
        item = tuple(asdict(queue_item).values())
        return item

The usage is as follows.

def main():
    #Prepare a queue
    priority_queue = PriorityQueue()
    for index in range(15):
        priority = index % 3
        priority_queue.put_item(priority=priority, item=index)
        print(f"[input] priority:{priority} value:{index}")

    #take out
    while not priority_queue.empty():
        priority, value, *_ = priority_queue.get_item()
        print(f"[output] priority:{priority} value:{value}")

if __name__ == "__main__":
    main()

[input] priority:0 value:0 [input] priority:1 value:1 [input] priority:2 value:2 [input] priority:0 value:3 [input] priority:1 value:4 [input] priority:2 value:5 [input] priority:0 value:6 [input] priority:1 value:7 [input] priority:2 value:8 [input] priority:0 value:9 [input] priority:1 value:10 [input] priority:2 value:11 [input] priority:0 value:12 [input] priority:1 value:13 [input] priority:2 value:14 [output] priority:0 value:0 [output] priority:0 value:3 [output] priority:0 value:6 [output] priority:0 value:9 [output] priority:0 value:12 [output] priority:1 value:1 [output] priority:1 value:4 [output] priority:1 value:7 [output] priority:1 value:10 [output] priority:1 value:13 [output] priority:2 value:2 [output] priority:2 value:5 [output] priority:2 value:8 [output] priority:2 value:11 [output] priority:2 value:14

You can see that the items with the same priority are taken in the order in which they were added to the queue.

Summary

We introduced the implementation of queues that can be acquired in the order in which they are added to the queue when the priorities are the same. It's not an exaggeration because it's just a Python object comparison method. I wrote it as a memorandum because it is a method that is not simply bound by the numerical value of priority. We hope for your reference.

Digression) I think that the implementation of overridden push / pop is necessary / unnecessary. If you want to get only the data managed by QueueItem (item in the above implementation), I think it can be used.

Recommended Posts

[Python] When the priority is the same in Priority Queue, it can be acquired in the order in which it was added to the queue.
[Python] tkinter Code that is likely to be reused
[Python] pandas Code that is likely to be reused
How to trick and use a terrible library that is supposed to be kept globally in flask
A program that determines whether a number entered in Python is a prime number
[Ln] How to paste a symbolic link in a directory is complicated
[Python] When the priority is the same in Priority Queue, it can be acquired in the order in which it was added to the queue.
I want to create a priority queue that can be updated in Python (2.7)
What to do when the value type is ambiguous in Python?
When I tried to run Python, it was skipped to the Microsoft Store
What to do when is not in the sudoers file.This incident will be reported.
What I did when I was angry to put it in with the enable-shared option
It is easy to execute SQL with Python and output the result in Excel
I was able to repeat it in Python: lambda
[Python] How to output the list values in order
[Python] Why the referenced objects have the same ID when the same integer is assigned to different variables
It was great to edit the Python file in the Raspberry Pi with Atom's remote function
[Python] It might be useful to list the data frames
Master the type in Python? (When should type check be done)
Scripts that can be used when using bottle in Python
Change the installation destination when --user is added to pip
Write a script in Shell and Python to notify you in Slack when the process is finished
NameError: global name'dot_parser' is not defined and what to do when it comes up in python
A simple reason why the return value of round (2.675,2) is 2.67 in python (it should be 2.68 in reality ...)
Be careful when specifying the default argument value in Python3 series
Delete a particular character in Python if it is the last
How to use the asterisk (*) in Python. Maybe this is all? ..
Review the basics in 1 minute! Python Priority queue for fast minimums
Have python check if the string can be converted / converted to int
How to display bytes in the same way in Java and Python
How to input a character string in Python and output it as it is or in the opposite direction.
In the python command python points to python3.8
I wrote the queue in Python
How to hide the command prompt when running python in visual studio 2015
[Python] Sweet Is it sweet? About suites and expressions in the official documentation
The day when basic authentication was added to the service operated by flask
Notify using Notification Center when the execution environment is macOS in Python
What to do when the warning "The environment is in consistent ..." appears in the Anaconda environment
Switch the module to be loaded for each execution environment in Python
How to automatically notify by phone when the python system is down
What is the fastest way to create a reverse dictionary in python?
[Python3] Code that can be used when you want to cut out an image in a specific size
The story that it turns blue when the data read by Pillow is converted so that it can be handled by OpenCV
I thought it was the same as python, and I was addicted to the problem that the ruby interpreter did not start.
In IPython, when I tried to see the value, it was a generator, so I came up with it when I was frustrated.
An engineer who has noticed the emo of cryptography is trying to implement it in Python and defeat it
[Python3] Code that can be used when you want to change the extension of an image at once