问什么决定选什么结构 — 用探测次数与高度预先计数

한 줄 요약

같은 '찾기' 라도 무엇을 묻느냐 — 정확히 한 건인지, 구간인지, 상위 몇 개인지 — 에 따라 맞는 구조가 다릅니다. 그리고 그 구조가 치를 비용은 시간을 재기 전에 탐사 횟수·트리 높이·교체 횟수 같은 결정적인 숫자로 먼저 셀 수 있습니다.

왜 이게 필요했나

파이썬에서 "빨리 찾고 싶다" 의 첫 답은 거의 늘 dict 입니다. 그런데 "지난 10분 동안 몇 건?", "점수 상위 20명", "주문 ID 1000번부터 2000번까지" 같은 질문에는 dict 가 답하지 못합니다. 해시는 순서를 버리는 대신 한 건 찾기를 싸게 만든 구조이기 때문입니다. bisect 문서도 같은 말을 합니다 — 이분 탐색은 값의 구간을 찾는 데 효과적이고, 특정 값을 찾는 데는 딕셔너리가 더 낫다.

반대로 순서가 필요해서 트리를 골랐는데 입력이 이미 정렬된 채로 들어오면, 균형을 잡지 않는 트리는 한쪽으로만 자라 사실상 연결 리스트가 됩니다. 자동 증가 ID, 시각 순 이벤트처럼 서비스의 입력은 생각보다 자주 정렬되어 있습니다. 구조를 고를 때는 "무엇을 묻나" 와 함께 "입력이 어떤 순서로 오나" 를 봐야 합니다.

어떻게 동작하나

해시 테이블과 적재율. 선형 탐사는 키의 집 칸 h(key) 에서 시작해 빈 칸이나 그 키를 만날 때까지 h+1, h+2… 로 한 칸씩 봅니다. 채운 비율 α(적재율)가 오르면 차 있는 칸이 이어진 덩어리가 길어지고, 덩어리에 떨어진 키는 그 끝까지 걸어야 합니다. Linear probing 항목은 이 현상을 1차 군집(primary clustering)이라 부르고, 무작위 해시 함수를 가정한 첫 이론 분석이 Knuth(1963)라고 적습니다. Sedgewick·Wayne 의 Algorithms 3.4절 Proposition M 은 균등 해싱 가정에서 평균 탐사 수를 찾기 성공 약 ½(1 + 1/(1−α)), 찾기 실패·삽입 약 ½(1 + 1/(1−α)²) 로 줍니다.

α	찾기 성공(이론)	찾기 실패(이론)
0.5	1.5	2.5
0.75	2.5	8.5
0.9	5.5	50.5

성공 쪽은 완만한데 실패 쪽은 제곱으로 뜁니다. 없는 키는 빈 칸을 만날 때까지 덩어리를 끝까지 걸어야 하기 때문입니다. 표를 키우는(리사이즈) 기준 적재율을 정하는 근거가 이 표입니다. 실습에서는 첫 칸도, 찾은 칸도, 마지막 빈 칸도 1회로 세서 이 식과 같은 정의로 잽니다.

이진 탐색 트리의 높이. 찾기 비용은 높이에 비례합니다. 이 실습은 높이를 뿌리에서 잎까지 가장 긴 경로의 노드 수로 셉니다(노드 하나면 1). 키 n 개로 만들 수 있는 가장 낮은 높이는 ceil(log2(n+1)) 이고, 정렬된 순서로 넣으면 n 입니다. 그 깊이를 재귀로 내려가면 sys.setrecursionlimit 문서가 말하는 인터프리터 스택 한도에 걸립니다. 한도를 올리기보다 반복문으로 쓰는 편이 안전합니다.

힙과 top-k. heapq 는 배열 하나로 최소 힙을 만듭니다. 불변식은 heap[k] <= heap[2k+1], heap[k] <= heap[2k+2] 이고, 가장 작은 값은 늘 heap[0] 입니다. 상위 k 개를 뽑을 때 최대 힙이 아니라 크기 k 의 최소 힙을 쓰는 이유가 여기 있습니다. 루트가 지금까지의 상위 k 가운데 가장 약한 항목, 곧 문턱이라서 새 항목은 루트와 한 번만 비교하고 대부분 버려집니다. 문턱을 넘을 때만 heapreplace 로 루트를 바꿉니다. 문서는 nlargest·nsmallest 가 작은 n 에 가장 좋고, 큰 n 이면 sorted() 가 더 효율적이라고 덧붙입니다. 또 우선순위가 같은 항목의 순서는 힙이 지켜 주지 않습니다. 문서의 우선순위 큐 예시는 들어온 순번을 두 번째 키로 넣어 동점을 가릅니다. 이 실습은 (점수, −id) 를 키로 써서 동점이면 id 가 작은 쪽을 남깁니다.

정렬 배열과 bisect. bisect_left 가 돌려주는 자리 ip 는 왼쪽이 전부 x 보다 작고 오른쪽이 전부 x 이상이 되게 배열을 가릅니다. 그래서 [lo, hi) 의 개수는 bisect_left(a, hi) − bisect_left(a, lo) 입니다. 경계에 같은 값이 몰려 있을 때 bisect_right 를 섞으면 hi 가 포함되거나 lo 가 빠집니다. 찾기는 O(log n) 이지만 문서대로 insort 는 삽입 단계 때문에 O(n) 입니다. 새 값이 늘 끝에 붙는 시각·자동 증가 ID 라면 append 만으로 정렬이 유지되어 이 약점이 사라집니다.

현장에서 만나는 모습

순위표를 Redis 의 Sorted Set 으로 만드는 방법과 만료 정책은 'Redis 와 캐싱' 코스가, 데이터베이스가 균형 트리(B+트리) 인덱스로 한 건 찾기와 구간 조회를 함께 푸는 이야기는 '데이터베이스 개념' 코스가, 그 인덱스를 옵티마이저가 실제로 쓰는지 실행 계획으로 확인하는 일은 'SQL 실전' 코스가 다룹니다. 이 모듈은 그 밑에 깔린 구조를 직접 만들어, 적재율 0.9 에서 없는 키 하나를 찾으려 몇 칸을 걷는지, 정렬된 입력이 트리를 몇 층으로 만드는지를 숫자로 확인하는 자리입니다.

다음 실습에서 할 것

못박은 해시 규칙으로 집 칸을 구하고, 선형 탐사 표를 만들어 적재율 0.5·0.75·0.9 의 평균 탐사 수를 이론값과 나란히 적습니다. 같은 키를 섞은 순서와 정렬된 순서로 트리에 넣어 높이를 비교하고, 최소 힙을 직접 만들어 heapq 와 pop 순서를 맞춘 뒤, 크기 k 힙으로 스트림의 상위 k 를, bisect 로 구간 개수를 셉니다. 마지막으로 작업 부하 네 가지에 구조를 고르고 여러분이 잰 숫자를 근거로 붙입니다.