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.
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.
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.
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