問題タブ [external-sorting]

ファイルに の配列がchar*あります。私が働いている会社では、データをフラット ファイルに保存しています。データが並べ替えられている場合もあれば、そうでない場合もあります。ファイル内のデータを並べ替えたい。

これで、これを行うコードを最初から書くことができました。もっと簡単な方法はありますか？

もちろん、その場での並べ替えが最適なオプションです。私は大きなファイルを扱っていて、RAM がほとんどありません。しかし、私はすべてのオプションを検討します。

すべての文字列は同じ長さです。

これはいくつかのサンプルデータです:

これは、長さ 28 の 3 つのレコードを表します。アプリは長さを認識しています。各レコードは CRLF ( \r\n) で終わりますが、この並べ替えには関係ありません。

私の最後の質問（複数の子プロセス）を参照して、私は現在、複数の子プロセスを使用して外部ソーティングの実装を作成しようとしています。

しかしもちろん、このコードはfscanfのために、入力ファイルから同じシーケンスのソートされた整数を出力します。たとえば、入力ファイルの先頭に5 1 4が含まれている場合、次のように出力されます。

（1番目の子）1 4 5
（2番目の子）1 4 5

（2つの子プロセスを使用）。fscanfは入力ストリームの先頭から整数の読み取りを開始するため。

今の私の問題は、前の子プロセスが残った時点からどのように数字を読み続けることができるかということです。たとえば、入力ファイルに5 1 4 8 5 10が含まれている場合、次のように出力できます。

（最初の子供）1 4 5

（2番目の子供）5 8 10

前もって感謝します;）

ディスク上にn個のオブジェクトを含む大規模なコレクションがあり、それぞれに可変サイズの文字列があるとします。プレーンな文字列比較を使用してこれらのオブジェクトのインデックスを作成する効率的な方法の一般的な方法は何ですか。サイズとI/Oのために、文字列全体をインデックスに格納することは長期的には禁止されますが、ディスクは待ち時間が長いため、参照のみを格納することもお勧めできません。

私は試行錯誤でBツリーのような設計を使用することを考えていましたが、このアプローチを使用したデータベース実装を見つけることができません。実際、主要なデータベースが文字列のインデックスをどのように実装しているかを見つけるのは困難です（SQLレベルの情報の膨大な結果で失われる可能性があります）。

TIA！

編集：タイトルを「大きな文字列を持つ保存されたオブジェクトの効率的な外部ソーティングと検索」から「文字列の外部インデックスの効率的な保存」に変更しました。

1行で構成されるファイルがあります：

この表現では、スペースが整数とコンマを区切ります。この文字列は非常に大きいため、RandomAccessFile.readLine() で読み取ることができません (ほぼ 4 Gb が必要です)。そのため、10 個の整数を格納できるバッファーを作成しました。私の仕事は、文字列内のすべての整数をソートすることです。

助けてくれませんか？

編集

@オスカー・レイエス

いくつかの整数シーケンスをファイルに書き込み、それから読み取る必要があります。実際、私はそれを行う方法を知りません。私は初心者です。そこで、文字を使用して整数を書き込むことにしました。整数間の区切り文字は「,」であり、シーケンス間の区切り文字は「\n\r」です。だから私はそれを読むモンスターを作成しました：

あなたがそれを行う方法をアドバイスできるなら、それをしてください=）

外部マージソートを書いています。それは次のように機能します: 大きなファイルから k 個のチャンクを読み取り、それらをメモリ内でソートし、k-way マージを実行して完了します。そのため、k-way マージ フェーズ中にファイルのさまざまな部分から順番に読み取る必要があります。それを行う最善の方法は何ですか: 複数の ifstream または 1 つの ifstream とシーク? また、簡単な非同期 IO 用のライブラリはありますか?

どちらの方がよいですか？1GBのメモリと100GBのファイルをソートするとします。

10 ウェイ マージの 1 つのインスタンスには次のものが必要です。

クイックソートには 100*7*2 (nlogn) 1GB のロードが必要ですか?

Javaに組み込みの外部ソートアルゴリズムが実装されていない特定の理由はありますか？

leveldbを使用してレコード（key-value）を格納しています。ここで、キーは64ビットハッシュで、値はdoubleです。例えれば、64ビットハッシュは顧客の一意のIDであり、アカウントの残高（つまり、アカウントにある金額）の2倍であると考えてください。データベースを口座残高で並べ替えて、口座残高が最も多い顧客を最初にリストしたいと思います。ただし、データベースはメモリに収まらないため、アカウントの残高で並べ替えるには、他の方法でデータベースを並べ替える必要があります。

STXXLの使用を検討していますが、データベースのコピーを1つのフラットファイルに作成する必要があります。その後、STXXLを使用して外部ソートを実行できます（これにより、多数の小さなファイルが作成され、ソートされてからマージされます）別の単一のフラットファイルに戻します）。データを並べ替えるより良い方法はありますか、それともSTXXL並べ替えを使用する必要がありますか？

この質問は簡単に思えますが、その背後にある実際の作業を理解できません。512 MB のチャンクに分割し、Map reduce を使用した Merge Sort を使用するように並べ替えます。

だからここに私が持っている実際の質問があります:

ファイルを 512 MB のチャンクに分割し、別のホスト マシンに送信して並べ替えるとします。これらのマシンがマージ ソートを使用したとします。ここで、2000 台のマシンでそれぞれ 2000、512 メガのチャンクをソートしたとします。それらをマージして戻すと、どのように機能しますか? またサイズが大きくなりませんか？たとえば、2 つの 512 MB をマージすると、RAM のサイズである 1024 MB になりますが、これはどのように機能しますか? サイズが 1 GB を超えるため、どのマシンも 512 MB を超えるチャンクを別のチャンクとマージすることはできません。

マージの最後に、2 つの 0.5 TB チャンクを別の 0.5 TB チャンクとマージするにはどうすればよいでしょうか。仮想メモリの概念はここで機能しますか?

私は自分の基本を明確にするためにここにいます。この非常に重要な質問を (正しく) 正しく尋ねていることを願っています。また、誰がこのマージを行うべきですか (ソート後)? 私のマシンですか、それとも 2000 台のマシンのいくつかですか?

メモリに収まらない大量のデータをソートする必要があります。これを行うことができるのは、「外部ソート」です。しかし、この大きなデータファイルをmmapし、「通常のデータ配列」であるため「qsort」を使用することは可能でしょうか? それが可能であれば、「外部ソート」との違いは何ですか?