자료구조의 선택 - 빅오와 메모리 접근·배열·연결 리스트·해시맵·트리 (CS 기초 4장)

이 장에서 배우는 것

3장에서 같은 연산 횟수라도 메모리 접근 순서에 따라 비용이 달라짐을 살폈다. 이번 장은 그 관점을 자료구조 선택에 적용한다. 선수지식은 목록·사전과 반복문이며 정렬 알고리즘의 구현은 필요하지 않다.

• 빅오가 표현하는 증가 형태와 생략하는 상수 비용을 구분한다.
• 배열과 연결 리스트를 위치 찾기와 지역성 관점에서 비교한다.
• 해시 조회의 평균과 최악을 가르는 충돌 조건을 설명한다.
• 반복 contains가 만드는 숨은 제곱 비용을 찾고 요구에 맞는 구조를 고른다.

개념

입력이 작을 때는 즉시 끝나던 중복 확인이 운영 데이터에서 오래 멈춘다. 반복문은 하나라서 선형 작업이라고 생각했지만 그 안의 포함 검사가 매번 목록을 훑고 있었다. 다른 곳에서는 목록을 해시맵으로 바꾼 뒤 메모리가 늘었다. 자료구조를 고를 때는 겉으로 보이는 반복문 수보다 어떤 연산을 얼마나 반복하는지 먼저 적어야 한다.

빅오는 증가 방향을 설명한다

복잡도는 입력이 커질 때 필요한 작업량이 어떤 형태로 증가하는지 설명한다. 원소 n개를 한 번 읽는 작업은 보통 선형이고, 각 원소마다 전체를 다시 읽으면 제곱 형태가 된다. n이 열 배가 되면 선형 작업은 대략 열 배, 제곱 작업은 대략 백 배로 커지는 관점을 얻는다. 이것은 모든 입력과 모든 기계에서 실행 시간이 정확히 그 배수가 된다는 보장이 아니다.

빅오는 상수 비용, 메모리 접근 특성, 실제 입력 분포를 모두 알려 주지 않는다. 작은 연속 배열의 검색이 초기 준비가 필요한 다른 구조보다 빨리 끝날 수 있고, 값 비교 자체가 비싸면 비교 횟수뿐 아니라 키의 길이도 중요해진다. 평균, 최악, 분할 상환의 조건도 서로 다르다. 조건을 빼고 O(1)이라고만 말하면 어떤 작업에서 그 약속이 깨지는지 알 수 없다.

배열과 연결 리스트는 위치 찾기가 다르다

고정 크기 원소가 연속된 배열에서는 시작 주소와 인덱스로 원소 위치를 계산할 수 있다. 인접 원소를 순서대로 읽기 쉬워 공간 지역성의 이점을 얻기도 한다. 중간에 새 원소를 넣으려면 뒤 원소를 옮겨야 할 수 있다. 크기가 늘어날 때 더 큰 저장 공간을 확보하는 방식의 동적 배열은 여유 용량과 재할당 정책까지 포함한다.

연결 리스트의 노드는 값과 다음 노드를 찾는 연결 정보를 갖는다. 원하는 노드까지 가려면 연결을 따라가야 하며, 노드가 메모리에 연속 배치된다는 보장은 없다. 삽입 위치의 노드와 필요한 앞뒤 연결을 이미 알고 있다면 연결 갱신 자체는 작다. 그러나 위치를 찾는 비용까지 자동으로 사라지지 않으므로 중간 삽입이 항상 빠르다는 말은 불완전하다.

Python list는 객체 참조를 담는 동적 배열로 이해해야 한다. 숫자 본체를 모두 고정 폭으로 연속 저장하는 모형과 다르고 객체 관리 비용도 있다. 양 끝에서 넣고 빼는 큐가 필요하면 deque처럼 그 연산에 맞춘 컨테이너가 후보가 된다. 이 장은 구현 API를 외우는 대신 조회·삽입·삭제의 위치와 빈도를 먼저 분류한다.

해시와 트리는 서로 다른 질서를 제공한다

해시 구조는 키에서 계산한 해시를 통해 후보 위치를 좁힌다. 서로 다른 키가 같은 해시나 같은 후보 위치로 모이면 충돌을 처리해야 하고 추가 비교가 발생한다. 키가 잘 분산되고 적절한 여유 공간이 있다는 조건에서 평균적으로 빠른 조회를 기대한다. 충돌이 심하거나 키 계산이 비싸면 입력 개수와 무관한 고정 시간으로 생각할 수 없다.

키가 존재하는 동안 동등성과 해시의 관계는 일관되어야 한다. 같다고 판단되는 두 키가 다른 해시를 내면 해시 구조의 탐색 계약을 깨뜨린다. 반대로 해시가 같다고 두 키가 같은 것은 아니므로 충돌 때 실제 동등성 확인이 필요하다. 예제에서는 일부러 같은 해시를 내는 서로 다른 키를 만들어 이 비용을 관찰한다.

트리는 비교 결과에 따라 작은 쪽과 큰 쪽으로 이동하는 질서를 제공할 수 있다. 균형이 유지되는 탐색 트리는 탐색 경로의 길이가 작게 증가하지만, 균형 조건이 없으면 길게 늘어져 선형 탐색과 비슷해질 수 있다. 정렬 순서 순회나 범위 탐색이 필요한 요구는 단순한 키 존재 확인과 다르다. 자료구조는 필요한 연산의 묶음으로 고른다.

배열은 연속 슬롯으로 위치를 계산하고 연결 리스트는 다음 노드를 따라간다. 해시 구조는 키로 후보 위치를 찾은 뒤 동등성을 확인한다.

직접 확인하기

실습은 Python 3 표준 라이브러리만 사용한다. 각 코드 블록을 별도 파일로 저장해 python3 파일명.py로 실행할 수 있다. 블록 사이에 공유하는 변수나 파일은 없다.

숨은 선형 탐색을 숫자로 드러낸다

def comparisons(n):
    values = list(range(n))
    count = 0
    for wanted in values:
        for value in values:
            count += 1
            if value == wanted:
                break
    return count
for size in [10, 100]:
    print(size, comparisons(size))

실행 결과다.

결과
----
10 55
100 5050

10개에서는 55번, 100개에서는 5050번 비교한다. 각각 앞에서부터 자신의 위치까지 찾기 때문에 단순히 입력 수만큼 비교하지 않는다. 실제 contains 구현을 호출하지 않고 비교를 펼쳐 적은 것은 숨어 있던 작업을 세기 위해서다. 두 입력의 비교 수 비율이 정확히 백 배가 아닌 이유는 작은 입력에서 낮은 차수의 항도 영향을 주기 때문이다.

allowed = list(range(0, 20, 2))
requests = [2, 3, 2, 8, 19]
by_list = [x for x in requests if x in allowed]
lookup = set(allowed)
by_set = [x for x in requests if x in lookup]
print(by_list)
print(by_set)
print("조회 결과 일치", by_list == by_set)

실행 결과다.

결과
----
[2, 2, 8]
[2, 2, 8]
조회 결과 일치 True

집합으로 바꾼 것은 허용 목록의 조회 구조뿐이고, 요청 순서와 중복은 그대로 보존했다. 결과 전체를 집합으로 바꾸면 중복 요청이 사라져 다른 작업이 될 수 있다. 조회가 한 번뿐이면 집합 구축 비용이 이익보다 클 수 있으므로 구축 횟수도 함께 센다. 실제 변경은 의미를 보존하는지 검증한 뒤 충분한 반복 조회가 있는지 확인한다.

충돌과 큐의 동작을 관찰한다

class Key:
    comparisons = 0
    def __init__(self, value):
        self.value = value
    def __hash__(self):
        return 0
    def __eq__(self, other):
        Key.comparisons += 1
        return isinstance(other, Key) and self.value == other.value
for size in [8, 32]:
    mapping = {Key(i): i for i in range(size)}
    Key.comparisons = 0
    found = Key(-1) in mapping
    print(size, found, "비교", Key.comparisons)

실행 결과다.

결과
----
8 False 비교 8
32 False 비교 32

모든 키의 해시를 0으로 만들었지만 값이 다르면 동등하지 않게 했다. 없는 키 하나를 찾을 때 입력이 늘면서 비교도 늘어나는 현상을 확인한다. 정확한 비교 횟수는 Python 구현의 탐색 방식에 따라 다를 수 있어 일반적인 규격값으로 취급하지 않는다. 이 예시는 충돌을 일부러 만든 교육용 코드이며 실제 키 형식으로 채택할 설계가 아니다.

from collections import deque
jobs = deque(["읽기", "계산", "응답"])
finished = []
while jobs:
    finished.append(jobs.popleft())
print(finished)
print("남은 작업", len(jobs))

실행 결과다.

결과
----
['읽기', '계산', '응답']
남은 작업 0

큐의 요구는 맨 앞 작업을 꺼내고 뒤에 새 작업을 붙이는 것이다. 같은 동작을 배열의 맨 앞 삭제로 만들면 구현에 따라 나머지 원소를 이동시켜야 할 수 있다. deque를 사용한 이유는 양 끝 연산이라는 요구에 맞추기 위해서이지 모든 인덱스 접근도 더 빠르기 때문이 아니다. 큐가 무한히 늘어나지 않게 하는 처리량과 용량 문제는 자료구조 선택만으로 해결되지 않는다.

환경별 차이

이 장의 비교 수 실험은 시간 측정과 분리되어 있어 다른 장비에서도 알고리즘의 숨은 반복을 확인하기 쉽다. 반면 충돌 예제의 정확한 호출 횟수는 구현 관찰값이므로 출력 파일에 실행 환경을 같이 남긴다. 객체 하나의 크기를 보고 전체 메모리를 곱셈으로 계산할 때는 공유 참조와 별도 원소 객체도 고려해야 한다. 메모리를 줄이려면 자료 개수, 중복 표현, 보관 기간을 함께 확인한다.

동일 입력으로 여러 구조를 비교할 때는 구축과 조회를 분리하되 최종 판단에서는 둘을 다시 합친다. 만들어 놓은 집합만 재는 실험과 매 요청마다 집합을 새로 만드는 서비스는 같은 작업이 아니다. 순서, 중복, 키 동등성 같은 업무 의미도 성능과 함께 검증한다. 빠른 코드가 다른 답을 만들면 성능 개선으로 받아들일 수 없다.

실무에서 자주 틀리는 것

반복문이 하나면 선형이다

증상은 입력이 늘 때 중복 확인 시간이 급격히 증가하는 것이다. 흔한 오진은 반복문이 하나이므로 외부 환경이 느려졌다는 판단이다. 실제 원인은 반복문 안의 포함 검사가 목록을 다시 훑는 것일 수 있다. 내부 연산을 펼쳐 비교 수를 세고 입력 크기를 단계적으로 늘린다. 조회 구조를 바꿀 때는 구축 비용과 결과의 중복 의미까지 확인한다.

연결 리스트는 중간 삽입이 항상 빠르다

증상은 연결 리스트로 바꿔도 편집 작업이 빨라지지 않는 것이다. 흔한 오진은 연결 갱신 코드가 비효율적이라는 판단이다. 실제 원인은 매번 삽입 위치까지 순차 탐색하는 비용일 수 있다. 위치 탐색과 연결 갱신을 따로 측정하고 노드를 이미 알고 있는지 확인한다. 별도 노드 할당과 메모리 접근 비용도 총 작업에 포함한다.

해시맵은 언제나 상수 시간이다

증상은 특정 키 집합에서 조회가 느려지는 것이다. 흔한 오진은 해시맵이므로 자료 분포와 무관하다는 판단이다. 실제 원인은 충돌이나 비싼 해시·동등성 계산일 수 있다. 충돌을 통제한 입력과 실제 입력을 비교하고 키 생성 비용도 분리한다. 평균 성능의 전제를 최악 성능 보장으로 바꾸지 않는다.

스스로 확인하기

문제와 해설

1. 입력 10개에서 55번, 100개에서 5050번 비교했다. 선형 증가라고 보기 어려운 이유를 설명하라.
2. 요청 [2, 3, 2]의 순서와 중복을 보존해야 한다. 전체 요청을 set으로 바꾸어도 되는지 판단하라.
3. 균형을 보장하지 않는 이진 탐색 트리에 키가 한쪽으로만 이어졌다. 탐색 비용을 설명하라.

해설 1 입력이 열 배일 때 비교가 약 91.8배 늘었다. 각 원소를 찾기 위해 앞에서부터 다시 훑는 누적 비용이며 큰 입력에서 제곱 형태가 지배한다.

해설 2 안 된다. 중복 2가 사라져 요구가 달라진다. 허용 목록의 조회 구조만 집합으로 바꾸고 요청은 순서대로 처리할 수 있다.

해설 3 경로가 원소 수만큼 길어질 수 있으므로 선형 탐색이 될 수 있다. 트리라는 이름만으로 로그 비용을 보장하지 않는다.

참고 자료: NIST 해시 테이블 용어 문서 · Python collections 문서 · Python 자료 모델의 해시 계약. 공식 자료는 사실 확인에만 사용했다. 설명·예제·문제·도식은 이 원고를 위해 새로 작성했다.

다음 장은 자료를 담은 프로그램이 운영체제 안에서 실행되는 단위로 넘어간다. 프로세스와 스레드가 주소 공간을 어디까지 공유하는지 살핀다.