平方根・閾値による軽重分類

概要

頻度・次数・更新回数を閾値でheavy/lightに分け、両側の計算量を均衡させる。

考え方

大きさBを境に軽い対象は全走査、重い対象は前計算や専用状態で扱う。重い対象が総量N/B個以下になることを利用し、軽い側と重い側の費用を釣り合わせる。

例えば総出現数Mの値別listを、長さ>Bならheavy、それ以外lightに分ける。heavy値は高々M/B種類である。query対象がlightならそのlistを直接O(B)走査し、heavyなら前計算した要約を読む、とすればQ queryの軽い側はO(QB)。各heavy値について全N対象へ要約を作る前処理はO(NM/B)。合計O(QB+NM/B)なので、B≈√(NM/Q)を取り、有効な範囲へclampして釣り合わせる。

閾値√Nが常に最適とは限らず、更新回数・query回数とheavy一種類の費用で式を立ててから選ぶ。動的分類なら値が閾値をまたぐ再構築や、入力全体で固定したheavy集合の正当性も数える。list走査のコストとheavy種類数の上界は異なる側へ課金する。

成立条件と計算量

典型的なN B+N²/Bの式ならB≈√Nだが、query数や更新費用で最適な閾値は変わる。重い対象数の上界を証明し、再分類費用と空間も数える。平方根を機械的に代入しない。

問題一覧

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

関連問題

前提・学習成果・出典

習得対象の目安: 青色(1600–1999)。頻度や次数で場合分けし、二つの計算量の釣合いから閾値を選ぶ。

対象色の読み方は本書の読み方を参照してください。

概念上の親: 軽重分類と償却解析で総仕事量を抑える。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-threshold-heavy-light

平方根・閾値による軽重分類

習得する技能

  • 頻度・次数・更新回数を閾値でheavy/lightに分け、両側の計算量を均衡させる。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: なし。

このUnitを直接前提とする単元: なし。

頻度・次数・更新回数を閾値でheavy/lightに分け、両側の計算量を均衡させる。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

このUnitでは扱わないもの

  • 平方根・閾値による軽重分類の発動条件・不変量を使わず、実装部品だけを偶然共有する解法。

根拠