0

1T (つまり 10^12) の数字で最も頻度の高い数字 (int 型) を見つける方法は?

私の前提は次のとおりです。

  • 私のメモリは 4G (つまり 4·10^9) バイトに制限されています。
  • すべての数値は、入力としてファイルに保存されます。
  • 出力は 1 つの数値のみです。
  • すべての数値 (int 型) は 1 つまたは複数のファイルに格納されます
  • ファイル構造は、バイナリまたは行で保存されます。

Edited at : 2013.04.22 17:08 コメントありがとうございます: さらに: - 外部ストレージは制限されません。

4

4 に答える 4

3

最初に、この問題は少なくとも要素の識別性の問題と同じくらい難しいことに注意してください。

したがって、ソリューションは同じアプローチに従う必要があります。

  1. sort (外部 sortを使用) を実行し、各数値の出現回数をカウントして最大値を探しながら反復します。
  2. ハッシュ ソリューション: 数値をメモリに収まるバケットにハッシュします (同じ数値の出現はすべて同じバケットにハッシュされることに注意してください)。バケットごとに、最も頻繁に使用される数値を見つけて保存します。次に、すべてのバケットからすべての候補を調べて、最適なものを選択します。
    ここでは、各バケットを (メモリ内で) 並べ替えて最も頻度の高い数を見つけるか、ヒストグラムを作成して(異なるハッシュ関数でハッシュ マップを使用)、バケット内の各項目の頻度を見つけることができます。
    バケットはディスクに書き込まれ、次々にメモリに読み込まれます。そのたびに、データのごく一部のみが RAM に保存されます。

別のよりスケーラブルなアプローチは、単純な map-reduce ステップで数ごとの出現回数をカウントし、それらの最大値を見つけるだけで、 map-reduce を使用することです。

map(number):
  emit(number,'1')
reduce(number,list):
  emit (number, size(list))

残っているのは、最大値の数値を見つけることです。これは、線形スキャンで実行できます。

于 2013-04-22T07:01:36.930 に答える
1

ファイルシステムを使用して数値のカウンターを保存するのはどうですか?

たとえば、数値が uint32 の場合、それぞれに 65536 個のファイルを含む 65536 個のディレクトリを作成できます。ディレクトリの名前は数値の上位 2 バイト、ファイル名 - 下位 2 バイトになります。番号 X に遭遇したら、それを 2 つの部分に分割してファイル名を取得し、そのファイルを開き、その中のカウンターをインクリメントします (または、ファイルがない場合は 1 を書き込みます)。

そのファイル構造を埋めた後、ツリーを再帰的にスキャンして、最大の価値を持つファイルを見つけることができます。

それは非常に遅くなりますが、RAM をほとんど消費しません。

于 2013-04-22T07:26:38.957 に答える
0

キーが数値、値がカウントであるハッシュテーブルを使用します。O(n) ハッシュテーブルにすべての数字を挿入する O(Unique numbers) 最も頻度の高いものを見つけます。

于 2013-04-22T07:07:14.137 に答える
0

強引な：

  • 覚えている= 0;
  • 繰り返す：
    • マークされていない最初の番号を取得し、ファイル内での出現回数をカウントします (n1)。
    • number が出現するたびに既読としてマークします。(空白feで上書き)
    • もし (n1 > 覚えている) 覚えている = n1;
于 2013-04-22T12:00:58.637 に答える