자료구조·컬렉션·이터레이터 심화

핵심 4종: list, tuple, dict, set

Python 코드의 대부분은 이 네 가지 타입 안에서 돌아간다. 용도를 혼동하면 성능과 가독성을 동시에 잃는다.

list의 내부 구조와 시간 복잡도

Python list는 C 동적 배열로 구현된다. append()는 공간이 충분하면 O(1), 재할당이 필요하면 O(n)이지만 amortized O(1)이다. 반면 insert(0, x)는 모든 원소를 오른쪽으로 밀어야 하므로 O(n)이다.

a = [1, 2, 3, 4, 5]
a.append(6)      # O(1) amortized — 끝 추가
a.insert(0, 0)   # O(n) — 앞 삽입은 비쌈
a.pop()          # O(1) — 끝 삭제
a.pop(0)         # O(n) — 앞 삭제도 비쌈
x in a           # O(n) — 선형 탐색

앞뒤 모두에서 O(1) 삽입·삭제가 필요하다면 collections.deque를 써야 한다. 원소 포함 여부를 빠르게 확인해야 한다면 set이 O(1)이다.

dict는 어떻게 O(1)을 달성하는가

Python dict는 오픈 어드레싱 방식의 해시 테이블이다. 키의 __hash__() 값으로 슬롯 위치를 계산하고 __eq__()로 실제 키를 비교한다.

Python 3.7부터 dict는 삽입 순서를 유지한다. 내부적으로 인덱스 배열과 엔트리 배열을 분리한 compact dict 구조를 써서, 메모리를 절약하면서도 순서를 보존한다. 이 덕분에 Python 3.7 dict는 이전 버전 대비 메모리 사용량이 약 20~25% 줄었다.

d = {}
d["a"] = 1   # __hash__("a") → 슬롯 결정
d["b"] = 2

print(d)  # {'a': 1, 'b': 2} — 삽입 순서 보장 (3.7+)
del d["a"]
print(d)  # {'b': 2}

tuple 언패킹 패턴

tuple은 단순히 불변 list가 아니라 여러 값을 묶는 레코드로 쓴다. 불변이므로 dict 키로 쓸 수 있고, namedtuple이나 dataclass의 기반이 된다.

# 언패킹
lat, lon = 37.5665, 126.9780

# 확장 언패킹 (Python 3+)
first, *rest = [1, 2, 3, 4, 5]   # first=1, rest=[2,3,4,5]
*head, last  = [1, 2, 3, 4, 5]   # head=[1,2,3,4], last=5

# swap
a, b = b, a  # Python에서 가장 Pythonic한 교환

collections 모듈: 내장 타입의 확장

표준 라이브러리의 collections 모듈은 실무에서 매우 자주 쓰이는 고성능 컨테이너를 제공한다.

deque: O(1) 양쪽 삽입·삭제

from collections import deque

q = deque([1, 2, 3], maxlen=5)
q.appendleft(0)   # O(1) 왼쪽 추가
q.popleft()       # O(1) 왼쪽 삭제
q.append(4)       # O(1) 오른쪽 추가

# maxlen이 있으면 가득 찼을 때 반대편 원소가 자동으로 제거된다
# → 최근 N개 유지 패턴(슬라이딩 윈도우)에 유용

BFS 구현, sliding window, circular buffer처럼 양쪽 끝을 모두 쓰는 알고리즘에 적합하다.

defaultdict: KeyError 없는 dict

from collections import defaultdict

counts = defaultdict(int)
for word in ["a", "b", "a", "c", "b", "a"]:
    counts[word] += 1  # 없는 키에 접근해도 int() = 0으로 초기화

# defaultdict(list)는 "key별로 값을 모을 때" 자주 쓴다
groups = defaultdict(list)
for k, v in [("a", 1), ("b", 2), ("a", 3)]:
    groups[k].append(v)
# defaultdict(<class 'list'>, {'a': [1, 3], 'b': [2]})

일반 dict에서 if key not in d: d[key] = [] 패턴이 반복된다면 defaultdict(list)로 교체한다.

Counter: 빈도 계산과 집합 연산

from collections import Counter

c = Counter("abracadabra")
print(c.most_common(3))  # [('a', 5), ('b', 2), ('r', 2)]

# Counter끼리 더하기·빼기 가능
c1 = Counter(a=3, b=2)
c2 = Counter(a=1, b=4)
print(c1 + c2)  # Counter({'b': 6, 'a': 4})
print(c1 - c2)  # Counter({'a': 2})  — 음수는 제거됨

namedtuple: 이름 있는 tuple 레코드

from collections import namedtuple

Point = namedtuple("Point", ["x", "y"])
p = Point(1.0, 2.0)
print(p.x, p.y)  # 1.0 2.0
print(p[0])       # 1.0 — tuple과 동일하게 인덱스 접근 가능

Python 3.7+에서는 @dataclass가 더 많이 쓰이지만, namedtuple은 불변성과 tuple 호환성이 함께 필요할 때 여전히 유용하다.

이터레이터 프로토콜

Python에서 for 루프나 list(), sum()이 동작하는 원리는 모두 이터레이터 프로토콜에 기반한다.

• 이터러블(Iterable): __iter__()를 구현한 객체. iter(obj)를 호출하면 이터레이터를 반환한다.
• 이터레이터(Iterator): __iter__()와 __next__()를 모두 구현한 객체. next(it)를 호출하면 다음 값을 반환하거나, 소진되면 StopIteration을 발생시킨다.

이터레이터를 직접 구현하는 예:

class Range:
    def __init__(self, start: int, stop: int) -> None:
        self.current = start
        self.stop = stop

    def __iter__(self) -> "Range":
        return self  # 이터레이터는 자기 자신을 반환

    def __next__(self) -> int:
        if self.current >= self.stop:
            raise StopIteration
        value = self.current
        self.current += 1
        return value

for n in Range(0, 4):
    print(n)  # 0 1 2 3

이터러블과 이터레이터는 다른 개념이다. list는 이터러블이지만 이터레이터가 아니다. iter(my_list)를 호출하면 list_iterator가 반환된다. 이터레이터는 __next__()를 가지며 상태를 갖는 커서다. 이터레이터 자체를 iter()에 넘기면 자기 자신을 반환하므로, 이터레이터는 이터러블이기도 하다.

제너레이터: 이터레이터를 간결하게 만드는 방법

클래스로 이터레이터를 구현하는 것은 번거롭다. 제너레이터 함수는 yield 키워드를 사용해 이터레이터를 훨씬 간결하게 만든다.

def count_up(start: int, stop: int):
    current = start
    while current < stop:
        yield current   # 값을 반환하고 실행을 일시 중단
        current += 1    # 다음 next() 호출 때 여기서 이어서 실행

for n in count_up(0, 4):
    print(n)  # 0 1 2 3

yield를 만나면 함수의 실행이 일시 중단되고 값이 반환된다. 다음 next() 호출 때 중단된 지점부터 이어서 실행된다. 이 "상태를 유지하는 일시 중단" 덕분에 클래스 없이도 이터레이터를 구현할 수 있다.

핵심 이점: 메모리 효율성

# list comprehension: 100만 개를 한꺼번에 메모리에 올림
total = sum([x * x for x in range(1_000_000)])

# generator expression: 한 번에 하나씩 계산, 메모리 O(1)
total = sum(x * x for x in range(1_000_000))

100만 개를 처리하는데 list comprehension은 수십 MB를 쓰지만, generator expression은 상수 메모리만 쓴다. Airflow hook 구현, Spark Python UDF, S3에서 큰 파일을 스트리밍으로 읽는 코드 등에서 중요한 패턴이다.

yield from: 서브제너레이터에 위임하기

Python 3.3(PEP 380)부터 yield from으로 다른 이터러블에 순회를 위임할 수 있다.

def flatten(items):
    for item in items:
        if isinstance(item, list):
            yield from flatten(item)  # 재귀적으로 내부 리스트를 순회
        else:
            yield item

list(flatten([1, [2, [3, 4]], 5]))  # [1, 2, 3, 4, 5]

단순 for item in sub: yield item을 yield from sub으로 대체하면 더 간결할 뿐 아니라, send()와 throw()도 투명하게 전달된다는 차이가 있다. asyncio가 도입되기 전에는 이 특성을 활용한 코루틴 패턴이 많았고, 현재도 서브제너레이터 위임 패턴은 유용하다.

리스트 컴프리헨션 vs 제너레이터 표현식

# 리스트 컴프리헨션: [] — 즉시 평가, 모든 결과를 메모리에 올림
evens_list = [x for x in range(10) if x % 2 == 0]

# 제너레이터 표현식: () — 지연 평가, 한 번에 하나씩
evens_gen = (x for x in range(10) if x % 2 == 0)

# dict 컴프리헨션
squares = {x: x**2 for x in range(5)}

# set 컴프리헨션
unique_squares = {x**2 for x in range(-3, 4)}

결과를 한 번만 순회하거나, 전체가 필요하지 않거나, 연쇄 파이프라인을 만든다면 제너레이터 표현식을 쓴다. 인덱스 접근이나 길이 확인이 필요하다면 list()로 변환한다.

itertools: 제너레이터 유틸리티 표준 라이브러리

itertools는 제너레이터 기반의 고성능 반복 도구를 제공한다.

import itertools

# 무한 제너레이터
counter    = itertools.count(10, 2)      # 10, 12, 14, …
cycle_abc  = itertools.cycle("ABC")      # A, B, C, A, B, C, …
repeat_x   = itertools.repeat(5, times=3) # 5, 5, 5

# 유한 이터레이터 도구
for combo in itertools.combinations([1, 2, 3], 2):
    print(combo)  # (1,2) (1,3) (2,3)

for perm in itertools.permutations("AB", 2):
    print(perm)   # ('A','B') ('B','A')

# 이터러블 연결
chained = itertools.chain([1, 2], [3, 4], [5])
# 1, 2, 3, 4, 5

# groupby: 정렬된 데이터에서 키로 그룹핑
data = sorted([("a", 1), ("b", 2), ("a", 3)], key=lambda x: x[0])
for key, group in itertools.groupby(data, key=lambda x: x[0]):
    print(key, list(group))
# a [('a', 1), ('a', 3)]
# b [('b', 2)]

itertools.islice는 무한 제너레이터에서 N개만 뽑을 때 쓴다.

first_5 = list(itertools.islice(itertools.count(0), 5))  # [0, 1, 2, 3, 4]

itertools.groupby는 연속된 같은 키를 묶으므로, 원하는 결과를 얻으려면 미리 정렬해야 한다. SQL의 GROUP BY와 다르다.

실전 패턴: 대용량 데이터 파이프라인

제너레이터는 데이터 파이프라인에서 특히 빛난다. 각 단계를 제너레이터로 만들면 전체 파이프라인이 메모리를 아끼면서 lazily 처리된다.

def read_lines(path: str):
    with open(path) as f:
        yield from f            # 한 줄씩 lazy하게 읽기

def parse_json_lines(lines):
    import json
    for line in lines:
        line = line.strip()
        if line:
            yield json.loads(line)

def filter_errors(records):
    for record in records:
        if record.get("level") == "ERROR":
            yield record

# 파이프라인 조합: 각 단계는 제너레이터
pipeline = filter_errors(parse_json_lines(read_lines("app.log")))

for record in pipeline:
    process(record)  # 한 번에 하나의 레코드만 메모리에 존재

이 패턴은 Airflow hook 구현, S3 스트리밍 다운로드, 대용량 CSV 처리 코드에서 반복적으로 나타난다. 전통적인 접근은 파일 전체를 메모리에 올리지만, 제너레이터 파이프라인은 가용 메모리와 독립적으로 파일 크기를 처리할 수 있다.

정리

Python의 자료구조와 이터레이터를 실무 관점에서 정리하면 다음과 같다.

1. list vs deque: 끝만 쓰면 list, 양 끝이 필요하면 deque. O(n) 앞 삽입을 반복하는 코드는 deque로 고쳐야 한다.
2. dict는 3.7+부터 순서 보장: OrderedDict가 필요한 경우는 순서 보존과 move_to_end() 같은 이동 연산이 함께 필요할 때로 좁혀졌다.
3. Counter와 defaultdict: 빈도 계산, 그룹핑 코드에서 if key not in d 패턴을 교체한다.
4. 이터레이터 프로토콜 이해: __iter__ + __next__의 동작을 알면 커스텀 컨테이너와 lazy 파이프라인을 설계할 수 있다.
5. 제너레이터로 메모리 관리: 대용량 데이터는 항상 제너레이터 체인으로 처리한다.
6. itertools: 표준 라이브러리에서 미리 만들어진 도구를 먼저 찾는다.

References

• Python Docs, collections module: https://docs.python.org/3/library/collections.html
• Python Docs, itertools module: https://docs.python.org/3/library/itertools.html
• PEP 380 – Syntax for Delegating to a Subgenerator (yield from): https://peps.python.org/pep-0380/
• Python Wiki, "TimeComplexity": https://wiki.python.org/moin/TimeComplexity
• Real Python, "Python Iterators and Iterables – Run Efficient Iterations": https://realpython.com/python-iterators-iterables/
• DataCamp, "Python Iterators and Generators Tutorial": https://www.datacamp.com/tutorial/python-iterators-generators-tutorial
• Python Generators Complete Guide 2026: https://universopython.com/en/blog/python-generators-complete-guide