6

使用可能なメモリ (数十ギガバイト) よりも大きく、可変長レコードを含むテキスト ファイルを並べ替えるための適切なアルゴリズムは何ですか? 私が見たすべてのアルゴリズムは、1) データがメモリに収まる、または 2) レコードが固定長であると想定しています。しかし、"BirthDate" フィールド (4 番目のフィールド) で並べ替えたい大きな CSV ファイルを想像してみてください。

Id,UserId,Name,BirthDate
1,psmith,"Peter Smith","1984/01/01"
2,dmehta,"Divya Mehta","1985/11/23"
3,scohen,"Saul Cohen","1984/08/19"
...
99999999,swright,"Shaun Wright","1986/04/12"
100000000,amarkov,"Anya Markov","1984/10/31"

そんなこと知ってる：

  1. これは1台のマシンで実行されます (分散されていません)。
  2. これを実行するマシンには、複数のプロセッサが搭載されています。
  3. 並べ替えるファイルは、マシンの物理メモリよりも大きくなる可能性があります。
  4. ファイルに可変長の行が含まれています。各行は固定数の列 (区切り文字で区切られた値) で構成されます。ファイルは特定のフィールド (つまり、ファイルの 4 番目のフィールド) でソートされます。
  5. 理想的な解決策は、おそらく「この既存の並べ替えユーティリティを使用する」ことですが、最適なアルゴリズムを探しています。
  6. 完全にコード化された実用的な答えは期待していません。「これをチェックしてください。これがどのように機能するか、またはこの問題でうまく機能する理由は次のとおりです」という行に沿ったものです。どこを見たらいいのかわからない…
  7. これは宿題じゃない！

ありがとう！♥</p>

4

4 に答える 4

3

このクラスのアルゴリズムは、外部ソートと呼ばれます。ウィキペディアのエントリをチェックアウトすることから始めます。いくつかの議論と指針が含まれています。

于 2010-12-15T18:24:02.397 に答える
1

次のリソースを提案してください。

マージソート: http://en.wikipedia.org/wiki/Merge_sort

Seminumerical Algorithms, vol 2 of The Art of Computer Programming: Knuth: Addison Wesley:ISBN 0-201-03822-6(v.2)

于 2010-12-15T18:39:55.467 に答える
0

標準のマージソートアプローチが機能します。一般的なスキーマは

  1. ファイルをほぼ同じサイズのN個の部分に分割します
  2. 各部分を並べ替えます（十分に小さい場合はメモリ内で、それ以外の場合は同じアルゴリズムを再帰的に適用します）
  3. ソートされたパーツをマージします
于 2010-12-15T18:34:11.210 に答える