우선순위 큐를 힙큐, 디큐로 변경

프로그래머스 "게임 맵 최단거리" 문제를 우선순위 큐로 풀었었는데, 동일한 기능을 하는 파이썬 내장 heapq를 사용하면 더 빠르게 임무를 수행한다고 한다. 그래서 우선순위큐를 힙큐로 변경해보기로 했다.

https://inspirer9.tistory.com/400

파이썬 우선순위큐, 게임 맵 최단거리, 길찾기

우선순위큐를 힙큐로 변경하는 이유

• 둘 다 O(logN)이고 같은 방식으로 사용되는데, 알고리즘 문제에서는 heapq를 쓰는게 좋다고 한다.
• heapq가 PriorityQueue보다 실행시간이 적게 걸린다.

우선순위큐를 힙큐로 변경하는 방법 

• 우선순위큐를 힙큐로 바꾸려면 왼쪽 항목들을 우측 항목으로 변경하면 된다.

PriorityQueue	heapq
from queue import PriorityQueue pq = PriorityQueue() pq.put(1) pq.put(3) pq.put(2) pq.get() # 1 pq.get() # 2 pq.get() # 3	import heapq pq = [] heapq.heappush(pq, 1) heapq.heappush(pq, 3) heapq.heappush(pq, 2) heapq.heappop(pq) # 1 heapq.heappop(pq) # 2 heapq.heappop(pq) # 3

 

우선순위큐 꿀팁

• PriorityQueue와 heapq는 최소 힙만 다룰 수 있기 때문에 큰 수부터 pop 하고싶을 때는 - 부호를 붙혀 push/pop한다.

소스코드

우선순위 큐 (PriorityQueue)

from queue import PriorityQueue

def solution(maps):
    #if maps[0][0] == 0: #이제 보니 이 부분 필요없네?
    #    return -1    

    pq = PriorityQueue() #그냥 큐를 써도 되는 듯... ㅡ.ㅡ;
    
    dist = 1
    sx, sy = 0, 0
    ex, ey = len(maps[0]), len(maps)
    INF = 10001 #float을 쓸 필요가 없음.
        #float("inf") #파이썬 3.5 이상에서 사용 가능
    
    for y in range(ey):
        for x in range(ex):
            if maps[y][x] != 0:
                maps[y][x] = INF
    
    pq.put([dist,(sx,sy)])
    while pq.empty() == False:
        t = pq.get()
        dist = t[0]
        x = t[1][0]
        y = t[1][1]
        
        if y == ey-1 and x == ex-1:
            return dist

        if dist < maps[y][x]:
            maps[y][x] = dist
            dist += 1
            if sx < x and dist < maps[y][x-1]:
                pq.put([dist,(x-1,y)])
            if x < ex-1 and dist < maps[y][x+1]:
                pq.put([dist,(x+1,y)])
            if sy < y and dist < maps[y-1][x]:
                pq.put([dist,(x,y-1)])
            if y < ey-1 and dist < maps[y+1][x]:
                pq.put([dist,(x,y+1)])

    return -1

힙 큐 (heapq)

import heapq

def solution(maps):
    #if maps[0][0] == 0: #이제 보니 이 부분 필요없네?
    #    return -1    

    pq = []
    
    dist = 1
    sx, sy = 0, 0
    ex, ey = len(maps[0]), len(maps)
    INF = 10001 #float을 쓸 필요가 없음.
        #float("inf") #파이썬 3.5 이상에서 사용 가능
    
    for y in range(ey):
        for x in range(ex):
            if maps[y][x] != 0:
                maps[y][x] = INF
    
    heapq.heappush(pq, [dist,(sx,sy)])
    while len(pq) > 0:
        t = heapq.heappop(pq)
        dist = t[0]
        x = t[1][0]
        y = t[1][1]
        
        if y == ey-1 and x == ex-1:
            return dist

        if dist < maps[y][x]:
            maps[y][x] = dist
            dist += 1
            if sx < x and dist < maps[y][x-1]:
                heapq.heappush(pq, [dist,(x-1,y)])
            if x < ex-1 and dist < maps[y][x+1]:
                heapq.heappush(pq, [dist,(x+1,y)])
            if sy < y and dist < maps[y-1][x]:
                heapq.heappush(pq, [dist,(x,y-1)])
            if y < ey-1 and dist < maps[y+1][x]:
                heapq.heappush(pq, [dist,(x,y+1)])

    return -1

디 큐(deque)

• 소문에는 더 빠르다는 디큐가 있어서 디큐로도 바꿔보았다.

from collections import deque

def solution(maps):
    q = deque()
    dist = 1
    sx, sy = 0, 0
    ex, ey = len(maps[0]), len(maps)
    INF = 10001

    for y in range(ey):
        for x in range(ex):
            if maps[y][x] != 0:
                maps[y][x] = INF

    q.append((dist, (sx, sy)))
    while q:
        dist, (x, y) = q.popleft()
        
        if y == ey - 1 and x == ex - 1:
            return dist
        
        if dist < maps[y][x]:
            maps[y][x] = dist
            
            for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nx, ny = x + dx, y + dy
                if nx >= 0 and nx < ex and ny >= 0 and ny < ey and dist + 1 < maps[ny][nx]:
                    q.append((dist + 1, (nx, ny)))
    
    return -1

속도 비교

• 빨라졌다. heapq가 더 빠르다. 근데 deque가 더 빠르다.

PriorityQueue	heapq	deque
정확성  테스트 테스트 1 〉 통과 (0.10ms, 10.4MB) 테스트 2 〉 통과 (0.06ms, 10.4MB) 테스트 3 〉 통과 (0.13ms, 10.5MB) 테스트 4 〉 통과 (0.09ms, 10.3MB) 테스트 5 〉 통과 (0.20ms, 10.4MB) 테스트 6 〉 통과 (0.27ms, 10.4MB) 테스트 7 〉 통과 (0.23ms, 10.3MB) 테스트 8 〉 통과 (0.13ms, 10.3MB) 테스트 9 〉 통과 (0.20ms, 10.3MB) 테스트 10 〉 통과 (0.21ms, 10.4MB) 테스트 11 〉 통과 (0.10ms, 10.4MB) 테스트 12 〉 통과 (0.08ms, 10.3MB) 테스트 13 〉 통과 (0.12ms, 10.4MB) 테스트 14 〉 통과 (0.11ms, 10.3MB) 테스트 15 〉 통과 (0.11ms, 10.4MB) 테스트 16 〉 통과 (0.06ms, 10.3MB) 테스트 17 〉 통과 (0.17ms, 10.3MB) 테스트 18 〉 통과 (0.08ms, 10.3MB) 테스트 19 〉 통과 (0.06ms, 10.1MB) 테스트 20 〉 통과 (0.03ms, 10.3MB) 테스트 21 〉 통과 (0.04ms, 10.3MB) 효율성  테스트 테스트 1 〉 통과 (84.16ms, 10.6MB) 테스트 2 〉 통과 (14.37ms, 10.5MB) 테스트 3 〉 통과 (39.36ms, 10.6MB) 테스트 4 〉 통과 (22.83ms, 10.4MB)	정확성 테스트 테스트 1 〉 통과 (0.03ms, 10.3MB) 테스트 2 〉 통과 (0.02ms, 10.4MB) 테스트 3 〉 통과 (0.04ms, 10.2MB) 테스트 4 〉 통과 (0.03ms, 10.2MB) 테스트 5 〉 통과 (0.05ms, 10.3MB) 테스트 6 〉 통과 (0.04ms, 10.2MB) 테스트 7 〉 통과 (0.11ms, 10.4MB) 테스트 8 〉 통과 (0.03ms, 10.2MB) 테스트 9 〉 통과 (0.09ms, 10.2MB) 테스트 10 〉 통과 (0.05ms, 10.3MB) 테스트 11 〉 통과 (0.03ms, 10.3MB) 테스트 12 〉 통과 (0.04ms, 10.3MB) 테스트 13 〉 통과 (0.03ms, 10.4MB) 테스트 14 〉 통과 (0.05ms, 10.2MB) 테스트 15 〉 통과 (0.04ms, 10.3MB) 테스트 16 〉 통과 (0.02ms, 10.2MB) 테스트 17 〉 통과 (0.06ms, 10.3MB) 테스트 18 〉 통과 (0.01ms, 10.3MB) 테스트 19 〉 통과 (0.01ms, 10.4MB) 테스트 20 〉 통과 (0.01ms, 10.3MB) 테스트 21 〉 통과 (0.01ms, 10.4MB) 효율성 테스트 테스트 1 〉 통과 (23.62ms, 10.1MB) 테스트 2 〉 통과 (4.68ms, 10.1MB) 테스트 3 〉 통과 (11.67ms, 10.2MB) 테스트 4 〉 통과 (6.93ms, 10.4MB)	정확성  테스트 테스트 1 〉 통과 (0.04ms, 10.1MB) 테스트 2 〉 통과 (0.03ms, 10.3MB) 테스트 3 〉 통과 (0.06ms, 10.3MB) 테스트 4 〉 통과 (0.04ms, 10.2MB) 테스트 5 〉 통과 (0.04ms, 10.3MB) 테스트 6 〉 통과 (0.07ms, 10.1MB) 테스트 7 〉 통과 (0.09ms, 10.1MB) 테스트 8 〉 통과 (0.05ms, 10.2MB) 테스트 9 〉 통과 (0.09ms, 10MB) 테스트 10 〉 통과 (0.05ms, 10.3MB) 테스트 11 〉 통과 (0.03ms, 10.2MB) 테스트 12 〉 통과 (0.03ms, 10.3MB) 테스트 13 〉 통과 (0.06ms, 10.3MB) 테스트 14 〉 통과 (0.03ms, 10.1MB) 테스트 15 〉 통과 (0.03ms, 10.3MB) 테스트 16 〉 통과 (0.02ms, 10.2MB) 테스트 17 〉 통과 (0.08ms, 10.1MB) 테스트 18 〉 통과 (0.01ms, 10.2MB) 테스트 19 〉 통과 (0.01ms, 10.2MB) 테스트 20 〉 통과 (0.01ms, 10.2MB) 테스트 21 〉 통과 (0.02ms, 10.3MB) 효율성  테스트 테스트 1 〉 통과 (11.94ms, 10.2MB) 테스트 2 〉 통과 (3.38ms, 10.3MB) 테스트 3 〉 통과 (8.15ms, 10.4MB) 테스트 4 〉 통과 (5.36ms, 10.3MB)

Priority Queue, heapq, deque 구현방식의 차이점

• 도대체 뭔 차이가 있어서 이런 결과가 나오는건가?

PriorityQueue	heapq	deque
클래스	모듈 (멀티쓰레드 지원)	모듈(Collections)
최소힙 heap와 동일한 기능 속도가 더 느림	최소힙, 최대힙(-사용) 다익스트라, 최소값이나 최대값을 빨리 찾아야 할 때 사용	선입선출, 후입후출, 선입후출, 후입선출 다됨. BFS에 사용

• 적절하지 않은 자료구조를 사용한 것으로 결론 ㅋㅋㅋ