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

"자료구조는 미래의 너와 맺는 거래야. 데이터를 이 모양으로 놓아둘 테니, 대신 내가 제일 자주 하는 일은 싸게 해달라는."

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

이름 만 개를 쪽지에 하나씩 적어서 신발 상자에 쏟아 넣었다고 해보자. 그 상자를 건네면서 묻는 거야. "여기 '피파' 있어?" 방법이 없어. 쪽지를 한 장씩 꺼내 보는 수밖에. 운이 나쁘면 만 장을 다 본다.

이번엔 같은 이름 만 개가 전화번호부에 있다고 하자. 가나다순으로 묶여 있고 쪽 번호까지 붙어 있어. 데이터는 그대로야. 이름도 그대로고. 그런데 "'피파' 있어?"가 몇 장 넘기면 끝나. 어디에 뭐가 있는지 배치가 정해져 있으니 볼 필요 없는 구간을 통째로 건너뛰거든. 바꾼 건 데이터가 아니라 데이터 주위의 구조야. 그것만으로 느린 질문이 빠른 질문이 됐어.

여기까지가 핵심이야. 자료구조는 "물건 두는 자리"가 아니라, 데이터에 '그 위에서 싸게 되는 연산'이 묶여 있는 것이야.

모든 구조는 거래다

입문자한테 아무도 짚어주지 않는 함정이 있어. 전부 싸게 가질 수는 없다는 것. 전화번호부는 조회를 싸게 만들지. 대신 묶인 책 한가운데에 새 이름을 끼워넣어 봐. 뒤에 있는 걸 전부 밀어야 해. 신발 상자는 조회가 최악이었지만 넣는 건 환상적이야. 쪽지 던져 넣으면 끝이거든.

그래서 자료구조는 전부 거래야. 제일 많이 하는 연산을 싸게 만들고, 덜 하는 쪽에서 값을 치러. 구조를 고른다는 건 결국 어떤 연산이 빨라질 자격이 있는지를 고르는 일이야. 외워야 할 건 구조가 아니라 그 결정을 내리는 눈이고.

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