1. 設問
ログプラットフォームがURLや商品IDなどのイベントキーを受け取りますが、イベント数は数十億件に達する可能性があります。固定メモリでadd(key)とestimate(key)を実装してください。おおよその出現カウントを返し、誤差、シャードのマージ、カウンターのオーバーフロー、および正確な構造が必要になるタイミングについて議論してください。
2. 制約と明確化事項
- 各イベントは一度だけ参照されます。すべてのキーをハッシュテーブルに収めることはできません。
- 過大推定は許容され、パラメータによって誤差の確率を制御します。
- 最初は非負の更新から始めます。削除、負の重み、および時間ベースの有効期限には追加の制約が必要です。
- シャードは、幅、深さ、ハッシュシード、およびカウンターのエンコーディングが一致している場合にのみ、直接マージできます。
3. コアアプローチ
Count-Min Sketch（CMS）は、w個の非負カウンターからなるd行を保持します。各行には、キーを1つの列にマッピングする独立したハッシュ関数があります。更新時は選択されたすべてのカウンターをインクリメントし、クエリ時は選択されたカウンターの最小値を返します。真のカウントは選択されたすべての行に現れますが、他のキーからの衝突はカウンターを加算することしかできないため、最小値は過小カウントしない上限値となります。
誤差epsilonと失敗確率deltaを使用する場合、一般的な選択肢はw = ceil(e / epsilon)およびd = ceil(ln(1 / delta))です。合計更新重みをNとすると、推定値は少なくとも1 - deltaの確率で、真のカウントプラスepsilon * N以下になります。これは確率的な誤差限界であり、すべてのクエリに対する絶対的な保証ではありません。
4. 参照実装
init(epsilon, delta):
w = ceil(e / epsilon)
d = ceil(ln(1 / delta))
table = array(d, w, fill=0)
seeds = choose_d_independent_seeds()
add(key, weight=1):
require weight >= 0
for row in 0..d-1:
col = hash(key, seeds[row]) mod w
table[row][col] += weight
total += weight
estimate(key):
values = []
for row in 0..d-1:
col = hash(key, seeds[row]) mod w
values.append(table[row][col])
return min(values)
merge(other):
require same w, d, seeds, counter encoding
for each cell (r, c):
table[r][c] += other.table[r][c]
total += other.total5. 計算量と正当性
各更新とクエリはd個のセルにアクセスするため、時間はO(d)です。空間はO(d * w)であり、一意なキーの数とは無関係です。非負の更新を行う場合、最小値は常に真の頻度以上を保ちます。幅を増やすと衝突による偏りが減少し、深さを増やすと誤差限界を超える確率が低下しますが、どちらもメモリとハッシュの処理量を線形に増加させます。
カウンターには十分な整数幅または明示的な飽和ポリシーが必要です。符号なしのラップアラウンドが発生すると、「過小カウントしない」という特性が無効になります。シャードのマージでは対応するセルを加算しますが、すべてのハッシュマッピングが一致している必要があります。異なるレイアウトを組み合わせると、解釈できない結果が生成されます。
6. 発展的なトピックと落とし穴
- CMSは既知のキーの概算カウントを回答するものであり、Top-Kを列挙するものではありません。その目的には候補セットを保持するか、ヘビーヒッター構造を使用してください。
- 衝突は過大推定しか引き起こさないため、推定値から正確な頻度や正確な一意集合を復元することはできません。
- 負の更新は単調性と単純な証明を損ないます。削除やスライディングウィンドウには、通常タイムバケットまたは減衰構造が必要です。
- ロールバック可能なバケット状態が保持されていない限り、古い合計を差し引くことで時間ウィンドウを維持することはできません。
7. 発展資料
CMSを正確なハッシュマップ、Bloom filter、HyperLogLog、およびFrequent Items Sketchと比較してください。これらはそれぞれ、頻度クエリ、メンバーシップ、カーディナリティ、およびヘビーヒッターの特定を対象としています。クエリ、誤差バジェット、削除の必要性、および候補キーを出力する必要があるかどうかに基づいて選択してください。
8. 面接の評価ポイント
カウンター行列を説明できるか
候補者は、独立した行ハッシュ、すべての行の更新、最小値の取得、およびなぜ衝突がカウンターを増加させることしかできないのかを説明できる必要があります。
誤差パラメータを提示できるか
候補者はepsilon、delta、w、d、および総重量Nを結びつけ、確率的限界と絶対的・正確な保証を区別できる必要があります。
エンジニアリング上の境界条件に対処できるか
候補者は、カウンターのオーバーフロー、シャードパラメータの互換性、セル単位の加算、ならびに負の重みやスライディングウィンドウに対する追加設計をカバーできる必要があります。
適合する構造を選択できるか
候補者は、CMSがTop-K、正確なメンバーシップリスト、または正確なカーディナリティを提供しないことを認識し、要件が変更された場合に正確なマップ、HLL、またはヘビーヒッター構造に切り替えられる必要があります。