[Python/파이썬] PriorityQueue & heapq / 우선순위큐와 힙큐

백준에서 문제를 풀다가 Priority Queue 와 Heapq 차이로 문제 시간에 걸릴 수도 안 걸릴 수도 있다는걸 알았다.

Priority Queue 와 Heaq의 차이를 알아보기 위해서 라이브러리를 뜯어서 맛보자

1. 라이브러리 속 코드

파이썬 3.9 버전 기준으로 queue 라이브러리 속 Priority Queue 는 아래와 같다.

from heapq import heappush, heappop

class PriorityQueue(Queue):
    '''Variant of Queue that retrieves open entries in priority order (lowest first).

    Entries are typically tuples of the form:  (priority number, data).
    '''

    def _init(self, maxsize):
        self.queue = []

    def _qsize(self):
        return len(self.queue)

    def _put(self, item):
        heappush(self.queue, item)

    def _get(self):
        return heappop(self.queue)

당황스럽다. 아니 Heapq 그 자체를 사용하고 있었다.

그저 Priorityqueue 는 객체 내부에 리스트를 보관해서 사용할 뿐이었다.

그래서 열심히 구글링 해보았다.

2. 오버플로우 속의 답

https://stackoverflow.com/questions/36991716/whats-the-difference-between-heapq-and-priorityqueue-in-python

What's the difference between heapq and PriorityQueue in python?

자세한 질문 내용과 답은 위의 링크를 들어가서 읽어 보는 것을 권한다.

요약하면 queue 속 PriorityQueue 는 Thread-Safe 하고 heapq는 Non-safe 하기 때문이라고 한다.

Thread Safe 하다는 것은 반드시 확인 절차를 걸쳐야 하기 때문에 확인하는 작업떄문에 더 느리다.

3. 실제 경험해보기

import random
import time
from queue import PriorityQueue
import heapq

N = 1000

print('순차적인 숫자 1 ~ 1000 push 후 pop')

start = time.time()
for _ in range(1000):
	que = PriorityQueue()
	for i in range(N):
		que.put(N)
	
	for i in range(N):
		que.get()

print('PriorityQueue : ', time.time() - start)

start = time.time()

for _ in range(1000):
	arr = []
	for i in range(N):
		heapq.heappush(arr, N)
	
	for i in range(N):
		heapq.heappop(arr)

print('Heapq : ', time.time() - start)

print('\n랜덤 숫자 1000번 push 후 1000번 pop 10회 평균')

sum_time = 0
for t in range(10):
	start = time.time()
	for _ in range(1000):
		que = PriorityQueue()
		for i in range(1000):
			que.put(random.randint(1, 10000))
		
		for i in range(1000):
			que.get()
	sum_time += time.time() - start

print('PriorityQueue : ', sum_time / 10)

sum_time = 0
for t in range(10):
	start = time.time()
	for _ in range(1000):
		arr = []
		for i in range(1000):
			heapq.heappush(arr, random.randint(1, 10000))
		
		for i in range(1000):
			heapq.heappop(arr)
	
	sum_time = time.time() - start

print('Heapq : ', sum_time / 10)

실제 걸린 시간 차이가 10배~30배 차이가 나는 것을 볼 수 있었다.

4. 정리

Thread-Safe를 요구하는 상황에서는 PriorityQueue

Thread-Non-Safe 해도 된다면 heapq 를 사용하는 것이 옳다.

코딩테스트로 문제를 푸는 상황이라면 Thread-Safe를 요구하지 않기 때문에 heapq를 써야할 것이다.

예시 문제 : 2021.08.26 - [Coding/BOJ] - [BOJ 1655 / 파이썬] 가운데를 말해요

[ 위 문제는 PriorityQueue 는 시간초과가 나오고 heapq 사용시 통과가 됨을 알 수 있다.]