Python collections

src/content/documents/python/python-collections-heapq-bisect.json

결론: 자료구조보다 작업을 먼저 이름 붙인다

양쪽 끝에서 넣고 빼는 큐는 deque, 키별 그룹핑은 defaultdict, 빈도는 Counter, 우선순위는 heapq, 정렬 리스트의 경계는 bisect가 의도를 드러낸다. 일반 list·dict로 충분하다면 전문 구조를 억지로 추가하지 않는다.

질문

우선 도구

대표 동작

양쪽 끝 큐·최근 N개

deque

append, popleft, maxlen

키별 자동 초기화

defaultdict

list·int factory

항목 빈도·상위 N개

Counter

missing→0, most_common

최소 우선순위 반복 추출

heapq

heappush, heappop

정렬 경계·삽입 위치

bisect

bisect_left, insort

deque: 큐와 고정 길이 슬라이딩 윈도우

deque는 양쪽 끝의 append·pop에 맞춘 double-ended queue다. list 앞쪽의 insert·pop은 나머지 항목을 이동시키지만 deque는 양끝 작업을 비슷한 성능으로 제공한다. 반면 중간 임의 인덱스 접근은 느려질 수 있으므로 list의 범용 대체품이 아니다.

from collections import deque

queue = deque(["a", "b"])
queue.append("c")
print(queue.popleft())
print(list(queue))

recent = deque(maxlen=3)
recent.extend([10, 20, 30, 40])
print(list(recent))
a
['b', 'c']
[20, 30, 40]

maxlen이 있는 deque가 가득 찬 뒤 새 항목을 append하면 반대쪽의 오래된 항목이 자동으로 빠진다. 최근 N개 관측값, 로그 tail, 고정 길이 윈도우에 적합하다. 내부 블록 구조는 API 계약이 아니므로 코드가 특정 구현 형태에 의존해서는 안 된다.

defaultdict: 키별 그룹핑과 get의 함정

defaultdict(factory)는 data[key]로 없는 키를 읽을 때 factory를 호출해 기본값을 저장한다. list factory는 그룹핑, int factory는 합계·카운트 초기화에 유용하다.

from collections import defaultdict

groups = defaultdict(list)
groups["A"].append(10)

print(dict(groups))
print(groups.get("B"))
print("B" in groups)
{'A': [10]}
None
False

get()은 일반 dict처럼 동작하며 default_factory를 호출하지 않는다. 그래서 groups.get('B')는 None이고 B 키도 생기지 않았다. 자동 초기화가 필요하면 대괄호 접근을 사용하고, 단순 조회라면 get을 사용한다.

Counter: 빈도와 가장 흔한 항목

Counter는 hashable 항목을 키로, 개수를 값으로 보관하는 dict 하위 클래스다. 없는 항목을 읽으면 KeyError 대신 0을 반환하고 most_common(n)으로 상위 빈도를 얻는다.

from collections import Counter

counts = Counter(["ok", "fail", "ok"])
print(counts["missing"])
print(counts.most_common(2))

counts["fail"] -= 1
print(dict(counts))
0
[('ok', 2), ('fail', 1)]
{'ok': 2, 'fail': 0}

개수를 0이나 음수로 바꿔도 키가 자동 삭제되지는 않는다. 필요하면 del counts[key]로 제거하거나, 양수 카운트만 남기는 연산을 의도에 맞게 선택한다.

OrderedDict가 여전히 필요한 경우

일반 dict도 현재 Python에서 삽입 순서를 보장하므로 단순히 순서를 기억하려고 OrderedDict를 선택할 필요는 줄었다. 항목을 양끝으로 재배치하는 move_to_end(), 앞뒤를 고르는 popitem(last=...), OrderedDict끼리의 순서 민감 동등성처럼 재정렬 중심 기능이 필요할 때 사용한다.

from collections import OrderedDict

order = OrderedDict([("a", 1), ("b", 2), ("c", 3)])
order.move_to_end("a")
print(list(order))
print(order.popitem(last=False))
['b', 'c', 'a']
('b', 2)

heapq: 최소 우선순위 큐와 top-k

heapq의 기본 API는 list를 min-heap으로 유지해 heap[0]에 최솟값이 오게 한다. 부모가 자식보다 작거나 같다는 heap invariant만 보장할 뿐 list 전체가 정렬된 것은 아니다.

import heapq

tasks = []
heapq.heappush(tasks, (2, "report"))
heapq.heappush(tasks, (1, "alert"))
heapq.heappush(tasks, (3, "archive"))

print(tasks[0])
while tasks:
    print(heapq.heappop(tasks)[1])
(1, 'alert')
alert
report
archive

튜플 우선순위가 같으면 다음 항목도 비교되므로 비교할 수 없는 payload를 직접 두면 오류가 날 수 있다. 실무 우선순위 큐는 고유한 증가 카운터를 중간 값으로 두는 패턴을 검토한다. 상위·하위 일부만 필요하면 nlargest()와 nsmallest()도 제공된다.

Python 3.14에는 max-heap 전용 함수가 추가되었지만 이전 지원 버전과 호환해야 하는 프로젝트도 많다. 이 글에서는 버전 전반에서 사용할 수 있는 min-heap API를 기준으로 설명한다. 음수 우선순위로 최대값을 흉내 내는 코드는 값의 의미와 변환을 명확히 할 때만 사용한다.

bisect: 정렬 경계와 삽입 위치

bisect_left는 이미 정렬된 list에서 값을 넣어도 순서가 유지되는 가장 왼쪽 위치를 반환한다. 동일 값의 존재 여부를 직접 반환하는 검색이 아니라 경계를 나누는 삽입점 검색이다.

from bisect import bisect_left, insort

boundaries = [60, 70, 80, 90]
print(bisect_left(boundaries, 80))

scores = [60, 70, 90]
insort(scores, 80)
print(scores)
2
[60, 70, 80, 90]

이진 탐색 단계는 O(log n)이지만 insort는 위치를 찾은 뒤 list에 삽입하며 항목 이동이 필요하다. 공식 문서대로 전체 삽입 비용은 선형 단계가 지배한다. 많은 동적 삽입을 해결하는 만능 정렬 컨테이너로 보면 안 된다.

key 인자는 Python 3.10에 추가되었다. 비싼 key 함수를 반복 검색에 쓰면 같은 항목을 다시 계산할 수 있으므로 공식 문서가 제안하듯 캐시하거나 미리 계산한 key list를 검색하는 방법을 검토한다.

종합 실습: 이벤트 한 번 순회해 여러 관점 만들기

from collections import Counter, defaultdict, deque
import heapq

events = [
    ("u1", "ok", 2),
    ("u2", "fail", 1),
    ("u1", "ok", 3),
]

recent = deque(maxlen=2)
by_status = defaultdict(list)
counts = Counter()
priority_queue = []

for user, status, priority in events:
    recent.append((user, status))
    by_status[status].append(user)
    counts[status] += 1
    heapq.heappush(priority_queue, (priority, user))

print(list(recent))
print(dict(by_status))
print(counts.most_common())
print(heapq.heappop(priority_queue))
[('u2', 'fail'), ('u1', 'ok')]
{'ok': ['u1', 'u1'], 'fail': ['u2']}
[('ok', 2), ('fail', 1)]
(1, 'u2')

같은 이벤트를 최근 기록, 상태별 그룹, 빈도, 다음 처리 우선순위라는 네 질문으로 나눴다. 자료구조는 원본 데이터의 종류가 아니라 얻고 싶은 관점에 맞춰 선택한다.

선택 체크리스트와 흔한 실수

☐ deque는 양끝 큐·최근 N개에 사용하고 중간 임의 접근용 list 대체로 쓰지 않는다.

☐ defaultdict의 대괄호 접근만 factory를 호출하며 get은 호출하지 않음을 안다.

☐ Counter의 없는 키는 0이고 0·음수 count가 자동 삭제되지 않음을 안다.

☐ 일반 dict의 순서 보존이면 충분한지, OrderedDict의 재정렬 기능이 실제 필요한지 구분한다.

☐ heap[0]만 최소임을 알고 heap list 전체를 정렬 결과처럼 사용하지 않는다.

☐ bisect 입력이 정렬되어 있는지 확인하고 insort의 list 삽입 비용까지 고려한다.

다음 글: 컴프리헨션으로 데이터 가공하기

적합한 컨테이너를 골랐다면 다음은 새 컨테이너를 만드는 표현법이다. 다음 글에서는 list·dict·set comprehension으로 변환과 필터를 읽기 좋게 쓰고, 일반 반복문이 더 나은 경계를 정한다.

참고 자료

댓글 0

댓글을 불러오는 중…