1

30 個のファイルがあり、いずれのファイルにも約 100,000 個のデータ項目が含まれています。データ項目は次のようになります。 1 つのファイルに一度だけ出現しましたが、他のファイルに出現する可能性があります。

10個のキーを取得するにはどうすればよいですか。その合計カウント値は、30個のファイルから上位10個すべてに含まれる必要があります。

どんな助けでも大歓迎です。

4

3 に答える 3

2

合計数が最大の10個のキーが必要だと仮定しています[最初のコメントによると、これは本当のようです]

設計ガイドライン:

  • データが大きすぎないため[ 32 ビット システムでの 100,000 * 30 整数は ~11.5 MB]、キーが大きすぎないと仮定すると1、データ セット全体がメモリに入力される可能性があります。
  • データがメモリ内にある場合、ディスク IO は RAM よりも非常に遅いため、データを並べ替えて複数回読み取ると、メモリ上のデータを操作するよりもはるかに遅くなることが予想されます。

アルゴリズム :

  1. ヒストグラムを作成します。これは実際にはHashMap:key->intであり、ファイルの読み取り中に入力されます。読み取っている各キーについて、それが既にヒストグラムにある場合は、カウントをヒストグラムの既存の値に追加し、存在しない場合は、(key,count) ペアをヒストグラムに追加します。【O(n)平均走行時間】
  2. ヒストグラムに値が入力されると (トップ 10 を見つけるのは簡単です)、min heapを作成し、ヒストグラムを反復処理します。もちろん、ヒープには常にトップ 10 の値と一致するキーが含まれている必要があります。このスレッドでそれを行う方法について説明があります。- 一定のトップ 10 の場合O(n)も同様です。
  3. 完了したら、ヒープにソリューションが含まれているので、そのコンテンツを表示するだけです。

利点:

  • ディスクの読み取りは 1 つだけです。ディスクはRAM よりもはるかに遅いため、これがボトルネックになる可能性があります。そのため、ディスクの読み取り/書き込みを最小限に抑えることが優先されます。
  • O(n)平均実行時間。

不利益：

  • ハッシュ関数が非常に貧弱な場合 [可能性は低い] - ハッシュ テーブルが原因で、解は 2 次時間の複雑さに減衰する可能性があります。
  • キーが大きくてメモリに収まらない場合は、さらに作業を行う必要があります。解決方法については、脚注 (1) を参照してください。

1:仮定が正しくない場合、キーをハッシュし、キーのみを保存することで部分的に解決できます。ディスク自体でハッシュの衝突が発生したら、等しいかどうかを確認します。読み取り数は増えますが、衝突の数は比較的少なく、優れたハッシュ関数を使用できます。また、それらのハッシュがメモリに衝突したキーをロードする必要があります [繰り返しますが、複数のディスク読み取りを避けるため]、それらのみをロードすると、要素の総数よりもはるかに小さい数になります。

于 2012-04-20T09:46:29.957 に答える
0

私は次のことを試みます：

  1. キーで各ファイルを並べ替える（たとえば、クイックソートを使用）（文字列の比較に使用するものに注意してください）-O（nlogn）。
  2. 等しいキーのカウント値をキーで合計することにより、すべてのファイルを1つにマージします（マージソートのマージルーチン-O（n）を使用）。一意のキーを持つ巨大なハッシュを取得します。
  3. カウント値でハッシュを並べ替えます-O（nlogn）。
于 2012-04-20T08:15:01.133 に答える
0
  1. 各ファイルをキーでソートします。キーを比較できない場合は...この回答を飛ばしてください~~~
  2. さて、複数のソートされたファイルと比較ルールがあります。多方向マージを試してください。これを慎重に行ってください。すべてのファイルの各キーをマージするときは、キーの順序に従ってカウントを合計してください。同時に、ここまでで上位 10 個のキーを維持するためのヒープを作成します。マージが完了すると、ヒープには上位 10 個のキーが含まれます。
于 2012-04-20T09:28:27.813 に答える