4

30GB以上のファイルがあります。そして、このファイルの各行はレコードと呼ばれ、2つの列で構成されています。これは次のようになります。

id1 id2

この2つのIDはすべて整数（32ビット）です。私の仕事は、すべての重複レコードを削除し、レコードを一意にし、最後に一意のid2をファイルに出力するプログラムを作成することです。

いくつかの制約があり、最大で30Gのメモリが許可され、非マルチスレッド/プロセスプログラムによって効率的にジョブを実行する方が適切です。

最初に私はアイデアを思いつきました。メモリの制約のため、ファイルをn回読み取ることにしました。それぞれ、。を含むレコードのみをメモリに保持しid1 % n = i (i = 0,1,2,..,n-1)ます。私が使用するデータ構造はでstd::map<int, std::set<int> >、id1をキーとして受け取り、id2をid1に配置しますstd::set。

このように、メモリの制約に違反することはありませんが、非常に低速です。std::mapとstd::setが大きくなると挿入速度が遅くなるからだと思います。さらに、ファイルをn回読み取る必要があります。各ラウンドが完了するとstd::map、次のラウンドのクリアも必要になりますが、これにも時間がかかります。

ハッシュも試してみましたが、 300Wのバケットでも衝突が多すぎるのではないかと思いました。

だから、私はここに私の問題を投稿します、あなたたちが私にもっと良いデータ構造やアルゴリズムを提供できるのを手伝ってください。

どうもありがとう。

PS

スクリプト（シェル、Python）が効率的に実行できる場合は、それが望まれます。

4

4 に答える 4

8

要件を見落としていない限り、Linux シェルでこれを実行できるはずです。

sort -u inputfile > outputfile

多くの実装sortでは、並列化された方法でも使用できます。

sort --parallel=4 -u inputfile > outputfile

最大 4 つの並列実行。

一時的sortに多くのスペースを使用する可能性があることに注意してください。/tmpそこでディスク容量が不足した場合は、-Tオプションを使用して、一時ディレクトリとして使用するディスク上の別の場所を指すことができます。

(編集:) 効率に関するいくつかのコメント:

  • (問題の解決策の) 実行中に費やされる時間のかなりの部分は、sort高度に最適化された IO に費やされます。
  • 非常に多くの RAM を持っていない限り、ソリューションはディスク上で一部の作業を実行することになる可能性があります (のようにsort)。繰り返しますが、これを最適化することは多くの作業を意味しsortますが、その作業はすべて完了しています。
  • の欠点の 1 つsortは、入力行の文字列表現を操作することです。独自のコードを作成する場合、できることの 1 つは (既に提案したことと同様)、入力行を 64 ビット整数に変換してハッシュすることです。十分な RAM がある場合、sortIO と整数の変換が非常に高速になる場合は、速度の点で優れている可能性があります。使いやすく、十分に速いので、努力する価値はないのではないかsortと思います.
于 2012-09-17T03:44:28.243 に答える
1

std::map<int, std::set<int> >使用する代わりにstd::unordered_multimap<int,int>。C++11 を使用できない場合は、自分で作成してください。

これstd::mapはノードベースであり、挿入ごとに malloc を呼び出します。これがおそらく遅い理由です。Unodered マップ (ハッシュ テーブル) を使用すると、レコード数がわかっている場合は、事前に割り当てることができます。しなくても、malloc の数は withのO(log N)代わりになります。O(N)std::map

これは、 external を使用するよりも数倍高速でメモリ効率が高いに違いありませんsort -u。

于 2012-09-17T05:38:58.067 に答える
1

たくさんのディスクを使わずにこれを効率的に行うことはできないと思います。どのような形式のデータ構造でも、非常に多くのメモリやストレージのオーバーヘッドが発生するため、アルゴリズムが影響を受けます。したがって、ここではソートソリューションが最適であると期待しています。

ファイルの大きなチャンクを一度に並べ替えてから、後でそれらのチャンクをマージ (つまり、マージソートから) できると思います。チャンクをソートした後、明らかにディスクに戻さなければなりません。入力ファイルのデータを置き換えるか（バイナリであると仮定）、一時ファイルに書き込むことができます。

レコードに関する限り、64 ビット値がたくさんあります。30GB の RAM を使用すると、一度に約 40 億のレコードを保持できます。それはかなり甘いです。クイックソートでその場で多くをソートすることも、マージソートでその半分をソートすることもできます。おそらく、そのサイズの連続したメモリ ブロックを取得することはできません。だからあなたはそれを壊さなければならないでしょう。これにより、クイックソートが少し複雑になるため、RAM でもマージソートを使用することをお勧めします。

最終的なマージ中に、重複を破棄するのは簡単です。マージは完全にファイルベースの場合もありますが、最悪の場合、入力ファイルのレコード数の 2 倍に相当する量のディスクを使用することになります (スクラッチ用に 1 ファイル、出力用に 1 ファイル)。入力ファイルをスクラッチとして使用できる場合は、RAM の制限またはディスクの制限 (存在する場合) を超えていません。

ここで重要なのは、マルチスレッドであってはならないという要件だと思います。これは、ディスクベースのストレージに適しています。時間の大半はディスク アクセスに費やされます。そのため、できるだけ効率的にそれを行うようにしたいと考えています。特に、マージソートを行っているときは、シークの量を最小限に抑える必要があります。バッファとして大量のメモリがあるので、それを非常に効率的にできると確信しています。

ファイルが 60GB で (バイナリだと仮定します)、約 80 億のレコードがあるとしましょう。RAM でマージソートを行う場合、一度に 15GB を処理できます。これは、ファイルの読み取りと (上書き) 書き込みを 1 回行うことになります。これでチャンクが 4 つになりました。純粋なマージソートを行いたい場合は、常に 2 つの配列だけを扱います。つまり、ファイルをさらに 2 回読み書きします。1 回目は各 15 GB チャンクを 30 GB にマージし、最後に 1 回マージします (重複の破棄を含む)。

それも悪くないと思います。出入り三回。クイックソートの良い方法を見つけた場合は、おそらくファイルのパスを 1 つ少なくすることでこれを行うことができます。連続していないメモリのチャンクを処理できるため、次のようなデータ構造dequeがうまく機能すると思います...しかし、おそらく独自に構築し、ソートアルゴリズムを微調整してそれを活用したいと思うでしょう。

于 2012-09-17T04:28:29.980 に答える
1

このアプローチは、ファイル内に重複するレコードがあまりない場合に役立ちます。

1回目のパス。Bloom filterにほとんどのメモリを割り当てます。入力ファイルからすべてのペアをハッシュし、結果をブルーム フィルターに入れます。ブルーム フィルターによって検出された各重複を一時ファイルに書き込みます (このファイルには、重複ではない誤検出も含まれます)。

2回目のパス。一時ファイルをロードし、そのレコードからマップを構築します。キーはstd::pair<int,int>、値はブール値のフラグです。このマップは、std::unordered_map/boost::unordered_map または std::map として実装できます。

3回目のパス。入力ファイルを再度読み取り、マップ内の各レコードを検索し、id2見つからないかフラグがまだ設定されていない場合は出力し、このフラグを設定します。

于 2012-09-17T10:02:42.087 に答える