ハッシュ・木・ヒープを自分で作って数える

한국어 원문으로 표시합니다.

목표

선형 탐사 해시 테이블·균형 없는 이진 탐색 트리·최소 힙·정렬 배열을 직접 만들어, 적재율에 따른 탐사 수, 입력 순서에 따른 트리 높이, top-k 의 힙 교체 횟수, 구간 개수를 결정적인 숫자로 셉니다. 마지막으로 작업 부하 네 가지에 구조를 고르고 그 숫자를 근거로 붙입니다.

왜 중요한가

자료구조의 비용은 시간을 재기 전에 셀 수 있습니다. 해시 테이블은 적재율이 오를수록 없는 키 하나를 찾으려 걷는 칸이 제곱으로 늘고, 균형 없는 트리는 정렬된 입력을 만나면 목록이 되며, 상위 k 를 뽑는 힙은 대부분의 항목을 비교 한 번으로 버립니다. 이 숫자들은 CPU 를 나눠 쓰는 파드에서도 흔들리지 않아서, 구조를 고른 이유를 남에게 증명하는 근거가 됩니다. 그래서 채점기는 시간을 재지 않고, 여러분의 클래스와 함수를 재료가 아닌 입력에 다시 돌려 탐사 수·높이·pop 순서·원소를 읽은 횟수를 기준 구현과 대조합니다.

재료

/opt/fixtures/svccs/structures/ 아래에 있습니다. 읽기만 하세요.

keys.txt        세션 토큰 8,000개(한 줄에 하나, 서로 다름)
absent.txt      keys.txt 에 없는 토큰 3,000개
bst_keys.txt    서로 다른 정수 3,000개(섞인 순서)
stream.csv      id,score 40,000줄(점수 동점이 많다)
timestamps.txt  정렬된 초 단위 시각 30,000줄(같은 초가 여러 번 나온다)
queries.json    {"queries": [[lo, hi], …]} 구간 질의
workload.json   {"scenarios": [{name, desc, …부하별 값, evidence: [근거 키 이름]}]}
params.json     table_size · loads(적재율 목록) · k

세는 규칙

집 칸     home(key, size) = int.from_bytes(sha256(key.encode("utf-8")).digest()[:8], "big") % size
탐사      집 칸부터 한 칸씩(끝에서 0 으로 돈다) 본다. 본 칸의 수가 탐사 수 — 첫 칸도 1회,
          찾은 칸도 1회, 없는 키면 마지막 빈 칸도 1회
높이      뿌리에서 잎까지 가장 긴 경로의 노드 수. 빈 트리 0, 노드 하나 1. 같은 키는 다시 넣지 않는다
top-k     점수 큰 순, 동점이면 id 작은 순. 크기 k 최소 힙(키 (score, -id)) — k 개가 찬 뒤
          새 항목의 키가 루트보다 크면 루트를 바꾸고 replacements +1
구간      [lo, hi) — lo 포함, hi 제외, lo >= hi 면 0

단계

/root/svccs/structures/home.json 에 size(params.json 의 table_size), first5(keys.txt 앞 5개 키의 집 칸 목록), distinct_homes(keys.txt 앞 size÷2 개 키의 집 칸 가운데 서로 다른 칸의 수)를 적습니다.
/root/svccs/structures/structs.py 에 LinearProbeTable(size) 를 만듭니다. insert(key) 는 본 칸의 수를 돌려주고(이미 있는 키면 넣지 않고 찾기까지 본 칸의 수), search(key) 는 (찾았나, 본 칸의 수) 튜플, len(table) 은 개수입니다.
params.json 의 loads 마다 새 표(크기 table_size)에 keys.txt 앞 n = round(α × size) 개를 넣고, /root/svccs/structures/loads.json 에 {"size", "rows": [{"alpha", "n", "avg_hit", "avg_miss", "max_hit", "theory_hit", "theory_miss"}]} 를 적습니다. avg_hit 는 넣은 키를 search 한 탐사 수 평균, avg_miss 는 absent.txt 를 search 한 평균, max_hit 는 넣은 키의 최대, theory_hit = ½(1 + 1/(1−α)), theory_miss = ½(1 + 1/(1−α)²), 평균과 이론값은 셋째 자리입니다.
같은 파일에 bst_height(keys) 를 만들고(균형 없는 BST 에 차례로 넣은 뒤의 높이), /root/svccs/structures/bst.json 에 n, shuffled_height(bst_keys.txt 파일 순서), sorted_height(오름차순), min_height(ceil(log2(n + 1)))를 적습니다.
같은 파일에 MinHeap 을 만듭니다 — push(value), pop()(가장 작은 값, 비었으면 IndexError), len(heap). 배열 하나로 직접 만들고 클래스 안에서 heapq 나 정렬을 쓰지 않습니다.
같은 파일에 top_k(stream, k) 를 만듭니다. stream 은 (id, score) 를 한 번만 훑을 수 있는 이터레이터이고, {"top": [[id, score], …], "replacements": 정수} 를 돌려줍니다(heapq 를 써도 됩니다). stream.csv 와 params.json 의 k 로 /root/svccs/structures/topk.json 에 k, n(데이터 줄 수), top, replacements 를 적습니다.
같은 파일에 count_range(values, lo, hi) 를 만듭니다(values 는 정렬된 시퀀스). values 를 복사하거나 훑지 말고 이분 탐색으로 셉니다. /root/svccs/structures/ranges.json 에 n(timestamps.txt 줄 수)과 counts(queries.json 순서대로의 개수)를 적습니다.
/root/svccs/structures/choose.json 에 workload.json 의 부하마다 {"choice", "evidence", "reason"} 을 적습니다. choice 는 hash·bst·heap·sorted_array 가운데 하나, reason 은 한 문장, evidence 는 그 부하의 evidence 목록에 있는 키를 아래 규칙으로 계산한 값입니다.

근거 숫자 규칙(8단계)

sessions      alpha = round(n / table_size, 3)
              avg_hit_probes = 크기 table_size 표에 keys.txt 앞 n 개를 넣고 그 키들을 search 한 평균(셋째 자리)
leaderboard   kept = k, replacements = top_k(stream.csv, k) 의 replacements
audit-window  count = timestamps.txt 에서 window 의 [lo, hi) 개수
order-ids     bst_height_sorted = bst_height(1, 2, …, n)
              bst_height_shuffled = bst_height(bst_keys.txt 앞 n 개, 파일 순서)

참고

채점기는 structs.py 를 불러옵니다. 파일을 읽어 결과를 만드는 코드는 if __name__ == "__main__": 아래나 별도 스크립트에 두세요.
흔한 실수: 탐사 수를 충돌 수(탐사 − 1)로 세는 것, 높이를 간선 수로 세는 것, 정렬된 입력에서 재귀가 한도를 넘는 것, 구간의 hi 쪽에 bisect_right 를 쓰는 것.
산출물은 세션이 끝나면 사라집니다. 필요하면 따로 보관하세요.

해시 규칙으로 집 칸을 구한다

keys.txt 앞 5개 키의 집 칸과, 앞 size÷2 개 키의 서로 다른 집 칸 수를 /root/svccs/structures/home.json 에 size·first5·distinct_homes 로 적는다.

hashlib.sha256(key.encode('utf-8')).digest()[:8] 을 int.from_bytes(…, 'big') 로 읽고 size 로 나눈 나머지입니다. 적재율 0.5 인데도 서로 다른 집 칸 수가 키 수보다 꽤 적다면, 그만큼의 키가 처음부터 남의 칸을 집으로 받은 것입니다.

선형 탐사 표를 만들고 탐사를 센다

/root/svccs/structures/structs.py 에 LinearProbeTable(size) 를 만든다 — insert 는 본 칸의 수, search 는 (찾았나, 본 칸의 수). 채점기가 변형 키로 탐사 수를 하나하나 기준 구현과 대조한다.

집 칸에서 시작해 빈 칸이나 그 키를 만날 때까지 한 칸씩 가며 셉니다. 첫 칸도 1회입니다. 끝 칸 다음은 0번 칸입니다(% size). 찾는 길과 넣는 길을 한 함수로 두면 두 연산의 세는 방법이 어긋나지 않습니다.

적재율이 탐사 수를 바꾼다

적재율 0.5·0.75·0.9 마다 새 표에 키를 넣고 있는 키·없는 키의 평균 탐사 수, 최대 탐사 수, 이론값을 /root/svccs/structures/loads.json 에 적는다.

적재율마다 표를 새로 만듭니다. 없는 키는 빈 칸을 만날 때까지 걸어야 해서 적재율이 오르면 찾기 성공보다 훨씬 빨리 늘어납니다. 이론값은 균등 해싱 가정의 근사라 실측과 조금 다를 수 있습니다.

정렬된 입력이 트리를 목록으로 만든다

structs.py 에 bst_height(keys) 를 만들고, bst_keys.txt 를 파일 순서와 오름차순으로 넣은 높이를 /root/svccs/structures/bst.json 에 적는다. 채점기는 정렬된 1,500개·중복·빈 입력으로도 부른다.

높이는 노드 수입니다(노드 하나면 1). 재귀로 내려가면 정렬된 입력에서 깊이가 n 이 되어 RecursionError 가 납니다 — 삽입을 반복문으로 쓰고, 새 노드를 단 깊이의 최댓값을 높이로 들고 다니면 따로 계산할 필요가 없습니다.

최소 힙을 직접 만든다

structs.py 에 MinHeap(push·pop·len)을 배열 하나로 만든다. 채점기가 push/pop 을 섞은 연산열(중복 값·튜플 포함)에서 pop 순서를 heapq 와 대조한다.

push 는 끝에 붙이고 부모보다 작은 동안 위로 올립니다. pop 은 루트를 꺼내고 마지막 원소를 루트에 둔 뒤, 두 자식 가운데 더 작은 쪽과 바꾸며 내립니다. 왼쪽 자식만 보면 pop 순서가 틀어집니다. 인덱스 k 의 자식은 2k+1, 2k+2 입니다.

크기 k 힙으로 스트림의 상위 k

structs.py 에 top_k(stream, k) 를 만들고, stream.csv 와 params.json 의 k 로 /root/svccs/structures/topk.json 에 k·n·top·replacements 를 적는다. 채점기는 동점이 많은 변형 스트림을 이터레이터로 넘긴다.

최대 힙이 아니라 크기 k 의 최소 힙입니다 — 루트가 문턱입니다. 동점에서 id 가 작은 쪽을 남기려면 키를 (score, -id) 로 둡니다. top 은 마지막에 힙을 점수 큰 순으로 정렬해 [id, score] 로 바꿉니다. stream 은 한 번만 훑을 수 있습니다.

정렬 배열과 bisect 로 구간을 센다

structs.py 에 count_range(values, lo, hi) 를 만들고 queries.json 의 구간 개수를 /root/svccs/structures/ranges.json 에 적는다. 채점기는 경계가 중복 값에 걸린 변형 배열로 부르고, 원소를 몇 번 읽는지도 센다.

bisect_left 는 '이 값보다 작은 원소의 수' 를 줍니다. 그러니 [lo, hi) 는 두 bisect_left 의 차입니다. hi 쪽에 bisect_right 를 쓰면 hi 와 같은 값까지 셉니다. values 를 list() 로 복사하거나 for 로 훑으면 원소를 전부 읽습니다.

작업 부하에 맞는 구조를 숫자로 고른다

workload.json 의 부하 네 가지마다 구조(hash·bst·heap·sorted_array)를 고르고, 근거 숫자를 앞 단계에서 만든 함수로 계산해 /root/svccs/structures/choose.json 에 적는다.

각 부하가 무엇을 묻는지(정확히 일치·상위 k·구간)와 입력이 어떤 순서로 오는지를 보세요. 늘 커지는 키를 균형 없는 트리에 넣으면 높이가 몇이 되는지는 4단계에서 이미 쟀습니다. 근거 규칙은 지시문의 '근거 숫자 규칙' 그대로입니다.