8

この問題に対する最適な解決策はありますか?

100 万個の電話番号のファイルから重複を見つけるアルゴリズムを説明してください。このアルゴリズムを実行すると、2 メガバイトのメモリしか使用できなくなります。つまり、すべての電話番号を一度にメモリにロードすることはできません。

私の「素朴な」ソリューションは、値を反復処理し、ファイルを一度にではなくチャンクでロードする O(n^2) ソリューションです。

i = 0 ～ 999,999 の場合

string currentVal = get the item at index i

for j = i+1 to 999,999
  if (j - i mod fileChunkSize == 0)
    load file chunk into array
  if data[j] == currentVal
    add currentVal to duplicateList and exit for

本当にユニークな方法でデータセット全体をロードし、番号が重複しているかどうかを確認できる別のシナリオが必要です。持ってる人いる？

4

4 に答える 4

8

ファイルを M 個のチャンクに分割します。各チャンクは、メモリ内で並べ替えるのに十分な大きさです。それらをメモリ内で並べ替えます。

2 つのチャンクのセットごとに、2 つのチャンクに対してマージソートの最後のステップを実行して、1 つの大きなチャンク (c_1 + c_2) (c_3 + c_4) .. (c_m-1 + c_m) を作成します。

ディスク上の c_1 と c_2 の最初の要素をポイントし、新しいファイルを作成します (c_1+2 と呼びます)。

c_1 の指す要素が c_2 の指す要素より小さい数である場合、それを c_1+2 にコピーし、c_1 の次の要素を指します。
それ以外の場合は、c_2 のポイントされた要素をコピーして、c_2 の次の要素をポイントします。

両方の配列が空になるまで、前の手順を繰り返します。2 つのポイント先の数値を保持するために必要なメモリ内のスペースのみを使用する必要があります。このプロセス中に、c_1 と c_2 の指す要素が等しい場合は、重複が見つかりました。これを 2 回コピーして、両方のポインターをインクリメントできます。

結果の m/2 配列は、同じ方法で再帰的にマージできます。正しい配列を生成するには、これらのマージ手順の log(m) が必要です。各番号は、重複を見つける方法で他の番号と比較されます。

あるいは、@Evgeny Kluev がほのめかしている手っ取り早い解決策は、メモリに十分収まる大きさのブルーム フィルターを作成することです。その後、ブルーム フィルターに失敗した各要素のインデックスのリストを作成し、これらのメンバーの重複をテストするためにファイルをもう一度ループすることができます。

于 2013-03-14T17:22:18.123 に答える
1

私は @airza のソリューションが気に入っていますが、考慮すべき別のアルゴリズムがあるかもしれません: おそらく、100 万の電話番号は非効率的に表現されているため、一度にメモリにロードすることはできません。つまり、電話番号ごとに必要以上のバイトを使用します。その場合、電話番号をハッシュし、ハッシュを (ハッシュ) テーブルに格納することで、効率的なソリューションを実現できる可能性があります。inハッシュ テーブルは、重複を簡単に見つけるためのディクショナリ操作 ( など) をサポートします。

具体的に言うと、各電話番号が 13 バイトの場合 ( の形式の文字列など(NNN)NNN-NNNN)、文字列は 10 億の数字の 1 つを表します。整数として、これは 4 バイトで格納できます (文字列形式の 13 ではなく)。次に、この 4 バイトの「ハッシュ」をハッシュ テーブルに格納できる可能性があります。これは、ハッシュされた 10 億の数値が、10 億ではなく、3 億 800 万の数値と同じスペースを占有するためです。不可能な数字 (市外局番000、555などのすべて) を除外することで、ハッシュ サイズをさらに縮小できる可能性があります。

于 2013-03-14T17:45:47.827 に答える
1

一時ファイルを保存できる場合は、ファイルをチャンクでロードし、各チャンクをソートしてファイルに書き込み、チャンクを繰り返し処理して重複を探すことができます。ファイル内の次の番号および各チャンク内の次の番号と比較することで、番号が重複しているかどうかを簡単に判断できます。次に、すべてのチャンクの次に小さい番号に移動し、番号がなくなるまで繰り返します。

ソートにより、実行時間は O(n log n) です。

于 2013-03-14T17:01:42.850 に答える