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

目標

線形プローブのハッシュテーブル・平衡化しない二分探索木・最小ヒープ・ソート済み配列を自分で作り、ロードファクターによるプローブ数、入力順序による木の高さ、top-kのヒープの入れ替え回数、範囲内の件数を、決定的な数字で数えます。最後に、4つのワークロードに構造を選び、その数字を根拠として添えます。

なぜ重要なのか

データ構造のコストは、時間を測る前に数えられます。ハッシュテーブルは、ロードファクターが上がるほど、存在しないキー1つを探すために歩くスロットが2乗で増え、平衡化しない木は、ソートされた入力に出会うとリストになり、上位kを取り出すヒープは、ほとんどの項目を1回の比較で捨てます。これらの数字は、CPUを共有するPodでも揺らがないので、構造を選んだ理由を他人に証明する根拠になります。そのため採点ツールは時間を測らず、あなたのクラスと関数を、用意された素材ではない入力で再実行し、プローブ数・高さ・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

このコードブロックの韓国語の説明は、順に、keys.txtはセッショントークン8,000個(1行に1つ、互いに異なる)、absent.txtはkeys.txtにないトークン3,000個、bst_keys.txtは互いに異なる整数3,000個(シャッフルされた順序)、stream.csvはidとscoreの40,000行(スコアの同点が多い)、timestamps.txtはソート済みの秒単位の時刻30,000行(同じ秒が何回も出てくる)、queries.jsonは範囲のクエリ、workload.jsonはワークロードごとの値と根拠となるキー名のリストを持つこと、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

このコードブロックの韓国語の説明は、順に、ホームスロットはキーのSHA-256の先頭8バイトをサイズで割った余りであること、プローブ数は、ホームスロットから1スロットずつ(末尾から0へ戻る)見たスロットの数で、最初のスロットも、見つけたスロットも、存在しないキーなら最後の空きスロットも、1回と数えること、高さは、根から葉までのもっとも長い経路のノード数で、空の木は0、ノード1つは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−α)²)で、平均と理論値は小数第3位です。
同じファイルに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)です。配列1つで自分で作り、クラスの中でheapqやソートを使いません。
同じファイルにtop_k(stream, k)を作成します。streamは(id, score)を1回だけ走査できるイテレーターで、{"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のいずれか1つ、reasonは1文、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 개, 파일 순서)

このコードブロックの韓国語の説明は、順に、sessionsではalphaはnをtable_sizeで割った値を小数第3位で丸めたものであり、avg_hit_probesはサイズtable_sizeのテーブルにkeys.txtの最初のn個を入れて、そのキーをsearchした平均(小数第3位)であること、leaderboardではkeptはkで、replacementsはtop_k(stream.csv, k)のreplacementsであること、audit-windowではcountはtimestamps.txtでのwindowの[lo, hi)の件数であること、order-idsではbst_height_sortedは1, 2, …, nのbst_height、bst_height_shuffledはbst_keys.txtの最初のn個をファイル順に入れたbst_heightであること、を述べています。

参考

採点ツールは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つずつ基準の実装と突き合わせます。

ホームスロットから始めて、空きスロットかそのキーに出会うまで、1スロットずつ進みながら数えます。最初のスロットも1回です。最後のスロットの次は、スロット0です(% size)。探す経路と入れる経路を1つの関数にまとめると、2つの操作の数え方がずれません。

ロードファクターがプローブ数を変える

ロードファクター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つなら1)。再帰で降りると、ソートされた入力では深さがnになり、RecursionErrorが発生します。挿入をループで書き、新しいノードを付けた深さの最大値を高さとして持ち歩けば、別に計算する必要がありません。

最小ヒープを自分で作る

structs.pyにMinHeap(push・pop・len)を、配列1つで作成してください。採点ツールが、pushとpopを混ぜた操作列(重複した値・タプルを含む)で、popの順序をheapqと突き合わせます。

pushは末尾に付けて、親より小さい間、上へ上げます。popはルートを取り出し、最後の要素をルートに置いてから、2つの子のうち小さいほうと入れ替えながら下げます。左の子だけを見ると、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は1回しか走査できません。

ソート済み配列とbisectで範囲内の件数を数える

structs.pyにcount_range(values, lo, hi)を作成し、queries.jsonの各範囲の件数を、/root/svccs/structures/ranges.jsonに書いてください。採点ツールは、境界が重複した値にかかる変形した配列で呼び出し、要素を何回読んだかも数えます。

bisect_leftは「この値より小さい要素の数」を返します。したがって、[lo, hi)は2つのbisect_leftの差です。hi側にbisect_rightを使うと、hiと同じ値まで数えます。valuesをlist()でコピーしたり、forで走査したりすると、要素をすべて読むことになります。

ワークロードに合う構造を数字で選ぶ

workload.jsonの4つのワークロードごとに構造(hash・bst・heap・sorted_array)を選び、根拠となる数字を、前のステップで作った関数で計算して、/root/svccs/structures/choose.jsonに書いてください。

各ワークロードが何を尋ねるのか(完全一致・上位k件・範囲)と、入力がどの順序で来るのかを見てください。常に大きくなるキーを、平衡化しない木に入れると高さがいくつになるかは、ステップ4ですでに測りました。根拠のルールは、指示文にある「根拠となる数値のルール」のとおりです。