最初に、この問題は少なくとも要素の識別性の問題と同じくらい難しいことに注意してください。
したがって、ソリューションは同じアプローチに従う必要があります。
- sort (外部 sortを使用) を実行し、各数値の出現回数をカウントして最大値を探しながら反復します。
- ハッシュ ソリューション: 数値をメモリに収まるバケットにハッシュします (同じ数値の出現はすべて同じバケットにハッシュされることに注意してください)。バケットごとに、最も頻繁に使用される数値を見つけて保存します。次に、すべてのバケットからすべての候補を調べて、最適なものを選択します。
ここでは、各バケットを (メモリ内で) 並べ替えて最も頻度の高い数を見つけるか、ヒストグラムを作成して(異なるハッシュ関数でハッシュ マップを使用)、バケット内の各項目の頻度を見つけることができます。
バケットはディスクに書き込まれ、次々にメモリに読み込まれます。そのたびに、データのごく一部のみが RAM に保存されます。
別のよりスケーラブルなアプローチは、単純な map-reduce ステップで数ごとの出現回数をカウントし、それらの最大値を見つけるだけで、 map-reduce を使用することです。
map(number):
emit(number,'1')
reduce(number,list):
emit (number, size(list))
残っているのは、最大値の数値を見つけることです。これは、線形スキャンで実行できます。