데크, 우선순위 큐
- 데크
양쪽 끝을 모두 추출할 수 있는 큐를 일반화한 추상 자료형
Douple-Ended Queue 의 줄임말
배열이나 연결 리스트 모두 가능하지만 이중 연결 리스트로 구현하는 것이 가장 잘 어울림
head, tail 이라는 이름의 두 포인터를 갖고 있다가 새로운 아이템 추가될 때 마다 앞쪽이나 뒤쪽으로 연결시킨 후 포인터 이동
- collection.deque
파이썬에서 데크 자료형 지원
인중 연결 리스트로 구현되어 있음
CPython 에서는 고정 길이 하위 배열을 지닌 이중 연결 리스트로 구현되어 있음
- 우선순위 큐
어떠한 특정 조건에 따라 우선순위가 가장 높은 자료형이 추출되는 자료형
큐나 스택과 같은 추상 자료형과 유사하지만 추가로 각 요소의 ‘우선순위’와 연관되어 있음
정렬 알고리즘을 사용하여 구현하며 대게 정렬에는 O(n log n) 이 필요하지만 단순 정렬보다 힙 정렬 등의 좀 더 효율적인 방법 활용
최단 경로를 탐색하는 다익스트라 알고리즘 등의 다양한 분야에서 활용되며 힙 자료구조와 관련이 깊음
- priorityQueue vs heapq
우선순위 큐는 heapq 를 통해 주로 사용됨
PriorityQueue 는 heapq 모듈의 메소드를 사용하므로 사실상 둘의 동일
PriorityQueue 는 스레드 세이프를 보장하지만 headq 는 보장하지 않음
파이썬은 GIL 의 특성상 멀티 스레딩이 거의 의미가 없기 때문에 굳이 멀티 스레드로 구현할 게 아니면 PriorityQueue 모듈 사용할 필요 없음
- GIL (Global Interpreter Lock)
전역 인터프리터 락의 약어
하나의 스레드가 자원을 독점하는 형태로 실행됨
멀티 코어가 당연한 세상에서 하나의 스레드가 자원 독점하는 형태는 매우 치명적
CPython 은 개발 초기에 번거로운 동시성 관리를 편리하게 하고 스레드 세이프하지 않은 CPython 의 메모리 관리를 쉽게 하기 위해, GIL로 파이썬 객체에 대한 접근 제한하는 형태로 설계