Python의 우선 순위 대기열 비교기

Python 우선순위 큐는 우선순위에 따라 항목을 꺼냅니다. 적절한 정렬 순서는 우선순위를 어떻게 표현하느냐에 따라 달라집니다. Python의 힙 도구는 기본적으로 가장 작은 항목을 먼저 반환하며, 사용자 지정 키나 비교 가능한 래퍼를 사용하면 다른 순서도 표현할 수 있습니다. 이 가이드에서는 queue.PriorityQueue, heapq, 정렬된 리스트, heapdict를 비교하고, 우선순위가 바뀌는 경우도 살펴봅니다.

Python의 우선순위 큐와 정렬 순서

우선순위 큐는 우선순위가 지정된 항목을 저장하고 정렬 규칙에 따라 다음 항목을 꺼내는 자료 구조입니다. 숫자가 클수록 “더 중요하다”는 의미를 우선순위 큐가 자동으로 알지는 못합니다. Python의 표준 힙 연산은 가장 작은 항목을 먼저 꺼냅니다. 큰 숫자의 우선순위를 먼저 처리하려면 음수로 저장하거나 래퍼 클래스에 비교 동작을 정의할 수 있습니다.

두 항목의 우선순위가 같다면 순번을 동점 처리 기준으로 포함하세요. 그러면 처리 순서를 예측할 수 있고, Python이 비교할 수 없는 실제 항목끼리 비교하려는 상황도 막을 수 있습니다. 항목을 넣기 전에 표현 방식을 정하세요. 일반 힙에 이미 저장된 우선순위를 바꾸더라도 힙 불변식이 자동으로 복구되지는 않습니다.

queue.PriorityQueue에 비교기 매개변수가 없는 이유

queue.PriorityQueue는 항목의 정렬 순서를 사용하는 스레드 안전 큐입니다. 생성자에는 비교기 매개변수가 없지만, 비교 가능한 항목을 넣을 수 있습니다. 흔히 튜플을 큐에 넣습니다. 첫 번째 튜플 필드가 우선순위를 정하고 두 번째 필드가 동점을 구분합니다. 예를 들어 put((priority, sequence, task))를 호출한 다음 get()을 호출하면 가장 작은 튜플이 먼저 반환됩니다. 숫자가 큰 우선순위를 먼저 반환해야 한다면 우선순위에 음수를 사용하세요.

두 작업의 우선순위가 같을 때는 순번 필드가 중요합니다. 순번이 없으면 튜플 비교가 작업 필드까지 이어지므로, 서로 다른 유형의 작업은 비교할 수 없을 수 있습니다. 스레드 동기화가 필요 없는 코드에서는 heapq를 사용해 큐의 동기화 메서드 없이 기본적인 힙 정렬을 구현할 수 있습니다. 어느 쪽도 별도의 비교 콜백을 받지는 않습니다.

heapq로 사용자 지정 순서 구현하기

사용자 지정 정렬 규칙을 Python이 비교할 수 있는 필드로 표현하세요. 이 예제는 점수가 큰 항목을 먼저 처리하기 위해 음수 점수를 사용하고, 동점이면 삽입 순서를 유지하도록 증가하는 순번을 사용합니다. 각 항목은 (negative score, sequence, task) 형식이므로 우선순위가 같은 항목의 작업 값끼리는 비교하지 않습니다.

다음 예제를 실행하세요. 코드 블록과 출력에 표시되는 레이블은 바이트 단위로 고정되어 영어로 남습니다.

이 섹션의 코드와 표시되는 레이블 또는 출력은 영어로 유지됩니다.

import heapq
from itertools import count

sequence = count()
queue = []

for score, task in [(7, "write"), (9, "review"), (9, "test")]:
    heapq.heappush(queue, (-score, next(sequence), task))

while queue:
    negative_score, _, task = heapq.heappop(queue)
    print(task, -negative_score)

review 9
test 9
write 7

이 방식은 키 기반 정렬을 지원하지만 범용 비교기 콜백을 제공하지는 않습니다. 더 복잡한 규칙이 필요하다면 비교 메서드로 원하는 순서를 표현하는 작은 클래스를 만들거나 각 항목을 비교 가능한 키의 튜플로 정규화하세요. 정렬 순서가 예측 가능하도록 동점 처리 기준을 명시하세요.

작은 우선순위 큐에 리스트 사용하기

큐가 작거나 항목을 묶음으로 추가할 때는 리스트가 간단합니다. (priority, task) 쌍을 저장하고 정렬한 다음, 다음 항목이 있는 쪽 끝에서 꺼내면 됩니다. 우선순위가 오름차순이고 가장 작은 값부터 처리하려면 내림차순으로 정렬한 뒤 끝에서 pop()을 호출하면 됩니다. 항목이 계속 들어온다면 삽입할 때마다 다시 정렬하세요. 리스트가 커질수록 전체를 반복해서 정렬하는 비용이 커지므로, 자주 추가하고 제거하는 작업에는 보통 힙이 더 적합합니다.

다음은 외부 의존성이 없는 리스트 예제입니다. 우선순위 값이 오름차순이므로 우선순위가 1인 작업이 먼저 제거됩니다. 코드 블록과 출력에 표시되는 레이블은 바이트 단위로 고정되어 영어로 남습니다.

이 섹션의 코드와 표시되는 레이블 또는 출력은 영어로 유지됩니다.

items = [(4, "report"), (1, "email"), (3, "meeting"), (2, "review")]
items.sort(reverse=True)

while items:
    print(items.pop())

(1, 'email')
(2, 'review')
(3, 'meeting')
(4, 'report')

쌍의 첫 번째 요소가 정렬 순서를 결정합니다. 두 우선순위가 같으면 다음으로 작업 문자열을 비교합니다. 삽입 순서를 유지해야 하거나 실제 항목끼리 비교할 수 없다면 순번을 추가하세요. 리스트 방식은 내용을 확인하기 쉽지만, 항목이 많고 자주 바뀌는 큐에서 전체를 반복해서 정렬하는 것은 비효율적입니다.

변경 가능한 우선순위에 heapdict 사용하기

큐에 들어 있는 동안 각 작업의 우선순위를 바꿔야 한다면 heapdict를 사용하세요. 서드파티 패키지는 pip install heapdict로 설치합니다. heapdict.heapdict 인스턴스는 키와 우선순위를 매핑합니다. 기존 키에 새 값을 할당하면 힙을 유지하면서 해당 키의 우선순위가 갱신됩니다. popitem()은 우선순위가 가장 낮은 키와 그 우선순위 값을 반환하며 항목을 제거합니다. 숫자가 큰 우선순위를 먼저 처리하려면 우선순위에 음수를 사용하세요.

패키지를 사용하는 기본 형태는 tasks = heapdict.heapdict()이며, 이어서 tasks["write report"] = 3처럼 값을 할당합니다. 나중에 tasks["write report"] = 0을 할당하면 해당 작업의 우선순위가 갱신됩니다. tasks.popitem()을 호출하면 우선순위가 가장 낮은 작업을 제거하고 그 키와 우선순위를 돌려받습니다. 이 예시는 서드파티 패키지가 설치되어 있어야 하므로 단독으로 실행할 수 있는 예제는 아닙니다.

매핑은 키마다 우선순위 하나만 저장하므로 큐에 넣는 작업마다 서로 다른 키를 사용하세요. popitem()으로 작업을 제거하면 더 이상 큐에 들어 있지 않습니다. 이는 heapq와 다릅니다. 일반 힙에서 기존 항목의 우선순위를 바꾸려면 대개 이전 항목을 직접 관리하거나 힙을 다시 만들어야 합니다.

적절한 방법 선택하기

여러 스레드가 동기화된 큐를 사용해야 하고 항목이 Python의 기본 비교 순서를 따를 수 있다면 queue.PriorityQueue를 선택하세요. 튜플 키나 비교 가능한 래퍼로 정렬 순서를 제어할 수 있지만 비교기 인수는 없습니다. 일반적인 단일 스레드 코드에서 간결하고 빠른 힙이 필요하고 키와 동점 처리 기준으로 사용자 지정 정렬을 표현할 수 있다면 heapq를 사용하세요. 자주 갱신할 필요가 없고 단순함이 중요한 작은 모음에는 정렬된 리스트가 적합합니다. 항목이 큐에 있는 동안 키로 우선순위를 바꿔야 한다면 heapdict를 선택하세요.

어떤 방법을 쓰든 작은 값과 큰 값 중 어느 쪽을 먼저 처리할지 정하고, 그 규칙을 일관되게 표현하며, 동점 처리 방식도 정의하세요. 삽입과 제거가 잦은 대규모 작업에서는 변경할 때마다 리스트 전체를 정렬하는 것보다 힙이 일반적으로 효율적입니다. 우선순위를 바꿔야 한다면 매핑 기반 힙을 사용하거나, heapq로 구현할 경우 오래된 항목을 직접 관리하세요.