何を問うかが構造を選ぶ — 探査回数と高さで先に数える

一言でいうと

同じ「検索」でも、何を尋ねるか(ちょうど1件なのか、範囲なのか、上位いくつなのか)によって、適した構造が異なります。そして、その構造が払うコストは、時間を測る前に、プローブ回数・木の高さ・入れ替え回数のような決定的な数字で、先に数えることができます。

なぜ必要なのか

Pythonで「速く探したい」ときの最初の答えは、ほとんどいつもdictです。しかし、「直近10分間で何件?」「スコア上位20人」「注文ID 1000番から2000番まで」のような問いには、dictは答えられません。ハッシュは順序を捨てる代わりに、1件の検索を安くした構造だからです。bisectのドキュメントも同じことを述べています。二分探索は値の範囲を探すのに効果的で、特定の値を探すには辞書のほうがよい、ということです。

逆に、順序が必要で木を選んだのに、入力がすでにソートされた状態で入ってくると、平衡化しない木は片側にだけ伸びて、事実上連結リストになります。自動採番のID、時刻順のイベントのように、サービスの入力は思ったより頻繁にソートされています。構造を選ぶときは、「何を尋ねるか」とともに「入力がどの順序で来るか」を見る必要があります。

どう動くのか

ハッシュテーブルとロードファクター: 線形プローブは、キーのホームスロットh(key)から始めて、空きスロットかそのキーに出会うまで、h+1、h+2…と1スロットずつ見ていきます。埋まっている割合α(ロードファクター)が上がると、埋まっているスロットが連なった塊が長くなり、塊に落ちたキーは、その端まで歩く必要があります。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

成功側は緩やかですが、失敗側は2乗で跳ね上がります。存在しないキーは、空きスロットに出会うまで塊を最後まで歩く必要があるからです。テーブルを拡大(リサイズ)する基準のロードファクターを決める根拠が、この表です。ラボでは、最初のスロットも、見つけたスロットも、最後の空きスロットも、1回と数えて、この式と同じ定義で測ります。

二分探索木の高さ: 検索のコストは高さに比例します。このラボでは、高さを、根から葉までのもっとも長い経路のノード数で数えます(ノードが1つなら1)。n個のキーで作れるもっとも低い高さはceil(log2(n+1))で、ソートされた順序で入れるとnです。その深さを再帰で降りていくと、sys.setrecursionlimitのドキュメントが述べるインタープリターのスタックの上限に引っかかります。上限を上げるよりも、ループで書くほうが安全です。

ヒープとtop-k: heapqは、配列1つで最小ヒープを作ります。不変条件はheap[k] <= heap[2k+1]、heap[k] <= heap[2k+2]で、最小の値は常にheap[0]です。上位k件を取り出すときに、最大ヒープではなくサイズkの最小ヒープを使う理由が、ここにあります。ルートが、これまでの上位kの中でもっとも弱い項目、つまりしきい値なので、新しい項目はルートと1回だけ比較され、ほとんどが捨てられます。しきい値を超えたときだけ、heapreplaceでルートを入れ替えます。ドキュメントは、nlargest・nsmallestは小さいnに最適で、大きいnならsorted()のほうが効率的だと付け加えています。また、優先度が同じ項目の順序は、ヒープが保ってくれません。ドキュメントの優先度キューの例では、入ってきた連番を2番目のキーとして入れて、同点を分けています。このラボでは、(スコア, −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+木)のインデックスで1件の検索と範囲の検索を一緒に解決する話は「データベースの概念」コースが、そのインデックスをオプティマイザーが実際に使うかどうかを実行計画で確認することは「SQL実戦」コースが扱います。このモジュールは、その下にある構造を自分で作り、ロードファクター0.9で存在しないキー1つを探すのに何スロット歩くのか、ソートされた入力が木を何層にするのかを、数字で確認する場所です。

次のラボですること

固定されたハッシュのルールでホームスロットを求め、線形プローブのテーブルを作って、ロードファクター0.5・0.75・0.9での平均プローブ数を理論値と並べて書きます。同じキーをシャッフルした順序とソートした順序で木に入れて高さを比較し、最小ヒープを自分で作ってheapqとpopの順序を一致させたあと、サイズkのヒープでストリームの上位kを、bisectで範囲内の件数を数えます。最後に、4つのワークロードに構造を選び、自分で測った数字を根拠として添えます。