리스트는 그냥 리스트가 아니야

"자료구조는 미래의 너랑 맺는 거래야: 데이터를 이렇게 배치해둘게, 그래서 내가 제일 자주 하는 일이 싸지도록."

같은 이름을 담는 두 가지 방법

이름 만 개를 낱장 쪽지에 적어 신발 상자에 쏟아 넣어서 너한테 줬다고 해봐. 그리고 물어: "여기 '피파' 있어?" 넌 쪽지를 하나씩 꺼내 보는 수밖에 없어, 찾거나 바닥을 칠 때까지. 최악의 경우 만 장.

이번엔 같은 이름 만 개인데 전화번호부에 있다고 해봐 — 가나다순으로, 묶여서, 쪽 번호까지. 같은 데이터. 같은 이름. 근데 이제 "'피파' 있어?" 는 몇 번 넘기면 끝나, 배치 덕에 통째로 건너뛸 수 있으니까. 데이터를 바꾼 게 아니야. 그 주위의 구조를 바꾼 거고, 느린 질문이 빠른 질문이 됐어.

이게 전부야. 자료구조는 "물건 두는 곳" 이 아니야. 데이터 + 그 위에서 싸게 되는 연산이야.

모든 구조는 거래다

입문자한테 아무도 안 알려주는 함정: 전부-싸게는 절대 못 가져. 전화번호부는 조회를 싸게 만들어 — 근데 묶인 책 중간에 새 이름을 끼워넣어 봐. 뒤를 다 밀어야 해. 신발 상자는 조회는 최악이었지만 삽입은 환상적이야: 그냥 쪽지 던져 넣으면 끝.

그래서 모든 자료구조는 거래야. 네가 제일 많이 하는 연산을 싸게 만들고, 덜 하는 데서 그 값을 치러. 구조를 고른다는 건 사실 어떤 연산이 빨라질 자격이 있는지를 고르는 거야. 구조를 외우는 게 아니라 — 그 결정이 능력이야.

Code

같은 데이터, 두 가지 거래·python

# 같은 이름 10,000개. 두 구조. 질문 하나: "이 이름 여기 있어?"
import time

names_list = [f"person_{i}" for i in range(10_000)]
names_set  = set(names_list)

target = "person_9999"  # 리스트한테 최악: 맨 끝에 있음

# list: 찾을 때까지 훑어야 함  -> O(n)
t = time.perf_counter()
for _ in range(10_000):
    _ = target in names_list
print("list   :", round(time.perf_counter() - t, 4), "s")

# set: 답으로 바로 해시  -> 평균 O(1)
t = time.perf_counter()
for _ in range(10_000):
    _ = target in names_set
print("set    :", round(time.perf_counter() - t, 4), "s")

# 데이터는 동일해. *거래*는 동일하지 않고.
# (set 이 왜 빠른지는 Hashing 트랙에서 정확히 배워.)

Exercise

네 물리적 공간을 둘러봐 — 책장, 양념 선반, 양말 서랍, 폰 홈 화면. 하나 골라서 답해: 그걸 배치한 사람이 어떤 연산을 싸게 만들었어 (찾기? 제일 자주 쓰는 거 집기? 새로 추가하기?), 그리고 그 배치가 대가로 뭘 귀찮게 만들었어? 두 문장으로 써봐.

Hint

귀찮은 게 하나도 없으면, 아직 거래를 못 찾은 거야 — 더 봐. 찾기 쉽게 정렬된 서랍은 보통 추가하기가 고역이야.

같은 이름을 담는 두 가지 방법

모든 구조는 거래다

Code

External links

Exercise

Progress

댓글 0