【要約】Boyer–Moore多数決法を図解｜異なる値を打ち消して過半数要素をO(n)で探す [Zenn_Python] | Summary by TechDistill
> Source: Zenn_Python
Execute Primary Source
// Problem
データ分析者が、大規模なログやアンケート結果から過半数要素を特定しようとする際、メモリ消費が課題となる。
- ・辞書を用いた集計は、要素の種類 k に比例して O(k) の空間を消費する。
- ・要素の種類が膨大になると、メモリ使用量が予測不能に増大し、システムを圧迫する。
- ・単なる「最多要素」の探索ではなく、厳密な「過半数」を低コストで判定する手法が求められる。
- ・メモリ制約のある環境では、従来のハッシュマップによる集計が困難な場合がある。
// Approach
全要素の出現回数を記録するのではなく、異なる値をペアで打ち消し合うアルゴリズムを採用する。
- ・1回目の走査では「候補」と「票数」の2つの状態のみを保持する。
- ・現在の値が候補と一致すれば票数を増やし、異なれば票数を減らす。
- ・票数が0になった時点で、次の値を新しい候補として設定し、票数を1にする。
- ・この操作により、異なる値のペアを順次打ち消し、過半数要素を候補として残す。
- ・2回目の走査で、残った候補の実際の出現回数をカウントし、過半数条件を満たすか検証する。
// Result
本手法の導入により、メモリ使用量を極限まで抑えた効率的な過半数判定が実現できる。
- ・空間計算量を O(1) に固定でき、要素の種類数に依存しない安定した動作が可能となる。
- ・時間計算量は O(n) であり、辞書を用いた手法と比較して計算速度の劣化がない。
- ・Pythonによる具体的な実装例が示され、空配列や過半数不在時の挙動も明確化されている。
- ・大規模データ処理におけるリソース管理の最適化に大きく寄与する。
Senior Engineer Insight
> 本手法の真価は、メモリ制約が厳しいストリーム処理にある。辞書を用いた集計は、要素の種類が多いとメモリ不足を招く。Boyer–Moore法は、空間計算量を O(1) に抑えられるため、リソース消費を予測しやすい。ただし、過半数の存在が保証されない場合は、必ず2回目の走査が必要だ。用途に応じた適切な選択が求められる。