There are two types of Python priority queues: I compared the speed.
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).
-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.
--- 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.
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