deque, 우선순위 큐 (Python Algorithm interview 10장)

파이썬 알고리즘 인터뷰 책을 정리한 포스트 입니다.

K개 정렬 리스트 병합

k개의 정렬된 리스트를 1개의 정렬된 리스트로 병합하라.

입력

[
	1->2->5,
	1->3->4,
	2->6
]

이 문제에서는 우선순위 큐로 해결할 수 있으며 PriorityQueue모듈을 사용하지 않고 heapq모듈을 사용한다. 이유에 대해서는 아래에서 설명한다.

for lst in lists:
    heapq.heappush(heap, (lst.val, lst))

주어진 입력을 위 코드로 최소 힙을 지원하는 heapq모듈에 저장하게 될 경우 lst.val이 작은 순서로 pop()을 진행하게 되면 중복된 값을 넣을 수 없다는 오류가 발생한다.

중복된 값을 피하기 위해 사용하진 않지만 구분할 수 있게 연결 리스트의 순서를 같이 삽입해 준다. heapq모듈에 저장하기 위한 수정된 코드는 다음과 같다.

for i in range(len(lists)):
    if lists[i]:
        heapq.heappush(heap, (lists[i].val, i, lists[i]))

heappop()으로 값을 추출하게 되면, 가장 작은 노드의 연결 리스트부터 차례대로 나오고 결과 노드에 하나씩 추가 된다. 힙에 아무 값도 남지 않을 때까지 반복하면 작은 노드부터 차례대로 연결된다.

while heap:
    node = heapq.heappop(heap) # 값 추출
    idx = node[i]
    result.next = node[2]

    result = result.next # heap에서 추출한 노드를 result의 다음 노드가 가리킬 수 있게 함
    if result.next:
        heapq.heappush(heap, (result.next.val, idx, result.next))

전체 코드

전체 코드는 다음과 같다.

def merge(self, lists):
    root = result = ListNode(None)
    heap = []

    # 각 연결리스트의 루트를 힙에 저장
    for i in range(len(lists)):
        if lists[i]:
            heapq.heappush(heap, (lists[i].val, i, lists[i]))

    # 힙 추출 이후 다음 노드는 다시 저장
    while heap:
        node = heapq.heappop(heap)
        idx = node[i]
        result.next = node[2]

        result = result.next
        if result.next:
            heapq.heappush(heap, (result.next.val, idx, result.next))

    return root.next

파이썬 전역 인터프리터 락(GIL)

파이썬은 강력한 언어지만 느린 언어로 알려져 있다. 느린 이유 중 하나는 GIL의 특징을 가지기 때문이다.

Global Interpreter Lock(GIL)은 하나의 스레드가 자원을 독점하는 형태이다. 하나의 스레드가 실행 중이면 다른 스레드는 선행되는 스레드가 끝나기를 기다렸다가 실행된다. 지금까지도 GIL을 걷어내지 못해 파이썬의 주요 특징으로 남아 있다고 한다.

PriorityQueue와 heapq

PriorityQueue는 내부적으로 heapq를 사용하기 때문에 동작은 동일하다. 차이점은 PriorityQueue클래스는 Thread-safe를 보장한다는 것이다. 멀티 스레드에도 안전한 동작을 하게 해주는 Thread-safe는 “함수나 변수, 객체 등이 여러 스레드로부터 동시에 접근이 이뤄져도 프로그램의 실행에 문제가 없음”을 뜻한다.

파이썬에서는 GIL특성상 멀티 스레딩이 의미가 없기 때문에 PriorityQueue의 Thread-safe는 큰 도움이 안된다. 또한 Thread-safe보장은 Locking을 제공하며, Locking Overhead가 발생한다. Locking Overhead는 어떤 처리를 하기 위한 간접적인 처리 시간, 메모리 등을 말하는데 Locking의 단위가 작아지면 Locknig Overhead는 증가하게 된다. 따라서 성능에도 영향을 미치게 된다.

이러한 이유로 위 문제에서 우선순위 큐 사용에 PriorityQueue를 사용하지 않고 heapq를 사용한 것이다.