Is the priority queue heapq in Competitive Pro (Python)? queue.PriorityQueue? Which one should I use?

There are two types of Python priority queues: I compared the speed.

Introduction

Glimpse,

class queue.PriorityQueue(maxsize=0) Priority queue constructor. maxsize is an integer that sets an upper limit on the number of elements that can be queued. Once this size is reached, inserts are blocked until the queue elements are consumed. If maxsize is less than or equal to 0, the queue size is infinite.

So queue.PriorityQueue seems to be good from the name. But the queue itself

The queue module implements multi-producer, multi-consumer queues. This is especially useful in multithreaded programming when information must be safely exchanged between multiple threads.

So it's obviously heavy (it seems to have some behavior for synchronization).

What i did

-Prepare an array a consisting of $ 2 \ cdot 10 ^ {5} $ random positive integers ($ \ leq 10 ^ {9} $) --Prepare an array b consisting of another $ 2 \ cdot 10 ^ {5} $ random positive integers ($ \ leq 10 ^ {9} $)

Then do the following $ 2 \ cdot 10 ^ {5} $ times. (This is the i-th operation)

--Take the smallest number from a. Then add the i-th element of b to a

Compare this with heapq and queue. In addition, when doing the above work, heapq is faster using pushpop than popping and pushing, so compare the speed as well.

result

--- Heapq, poppush
elapsed_time:0.15400314331054688[sec]
--- Heapq, pop then push
elapsed_time:0.20299005508422852[sec]
--- Queue
    Step1: create init queue
elapsed_time:0.37195301055908203[sec]
    Step2: pop then push
elapsed_time:0.873100996017456[sec]

So use heapq when using priority queues in Python (in competitive programming). Since queue.PriorityQueue does not have init, it pushes the array a to q, which is created one by one.

code

import queue
import heapq

import time
import random
from copy import deepcopy
n = 2 * 10**5

inqueue = [random.randint(0, 10**9) for _ in range(n)]
inheapq = deepcopy(inqueue)

data = [random.randint(0, 10**9) for _ in range(n)]

resqueue = []
resheapq = []

print("--- Heapq, poppush")
start = time.time()
heapq.heapify(inheapq)
for i in range(n):
    x = heapq.heappushpop(inheapq, data[i])
    resheapq.append(x)
elapsed_time = time.time() - start
print("elapsed_time:{0}".format(elapsed_time) + "[sec]")

print("--- Heapq, pop then push")
start = time.time()
heapq.heapify(inheapq)
for i in range(n):
    x = heapq.heappop(inheapq)
    resheapq.append(x)
    heapq.heappush(inheapq, data[i])
elapsed_time = time.time() - start
print("elapsed_time:{0}".format(elapsed_time) + "[sec]")

print("--- Queue")
print("    Step1: create init queue")
start = time.time()
q = queue.PriorityQueue(n)
start = time.time()
for i in range(n):
    q.put(inqueue[i])
elapsed_time = time.time() - start
print("elapsed_time:{0}".format(elapsed_time) + "[sec]")
print("    Step2: pop then push")
start2 = time.time()
for i in range(n):
    x = q.get()
    resqueue.append(x)
    q.put(data[i])
elapsed_time = time.time() - start2
print("elapsed_time:{0}".format(elapsed_time) + "[sec]")

Recommended Posts

Is the priority queue heapq in Competitive Pro (Python)? queue.PriorityQueue? Which one should I use?
[Python] DI (Dependency Injection) container Which one should I use?
I wrote the queue in Python
[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.
% And str.format () in Python. Which one do you use?
I want to use the R dataset in python
How to use the asterisk (*) in Python. Maybe this is all? ..
Review the basics in 1 minute! Python Priority queue for fast minimums
Use fabric as is in python (fabric3)
I wrote the stack in Python
After all, what should I use to do type comparisons in Python?
Ant book in python: Priority queue self-implementation
What is "mahjong" in the Python library? ??
How to use is and == in Python
I want to create a priority queue that can be updated in Python (2.7)
How to use the C library in Python
What is wheezy in the Docker Python image?
I tried simulating the "birthday paradox" in Python
I tried the least squares method in Python
About the difference between "==" and "is" in python
I implemented the inverse gamma function in python
The one that displays the progress bar in Python
[Question] What happens when I use% in python?
Use the LibreOffice app in Python (3) Add library
I want to display the progress in Python!
Here is one of the apps with "artificial intelligence" that I was interested in.
How to check in Python if one of the elements of a list is in another list
[New Corona] Is the next peak in December? I tried trend analysis with Python!