64ビットのLinuxボックスでgcc4.7.2を使用しています。
外部merge-sortの最終マージの一部として読み取る必要がある20個の大きなソート済みバイナリPODファイルがあります。
通常、ディスクへの書き込みを行う前にmmap、すべてのファイルを読み取り、aを使用しmultiset<T,LessThan>て小さなものから大きなものへのマージソートを管理します。mmap
std::mutexただし、これらの各ファイルを保持すると、ファイルを逆方向に読み取る2番目のスレッドを作成し、同時に大きいものから小さいものに並べ替えることができることに気付きました。事前に、最初のスレッドが正確にn / 2の要素を取り、2番目のスレッドが残りを受け取ると決定した場合、出力側にミューテックスは必要ありません。
読み取りロックの競合は、この特定のケースでは平均して20分の1になると予想されるため、許容範囲内です。
さて、これが私の質問です。最初のケースでは、で呼び出す必要madviseがあることは明らかですが、ファイルを逆方向に読み取っている2番目のケースで何をすべきかわかりません。MADV_SEQUENTIAL
MADV_REVERSEマニュアルページには何も表示されません。使用する必要がありますMADV_NORMALか、それともまったく電話madviseしないでください。
データの量が多すぎてメモリに収まらない場合は、外部ソートが必要であることを思い出してください。したがって、ディスクを一時ストアとして使用するためのより複雑なアルゴリズムが残されています。分割統治アルゴリズムでは、通常、データを分割し、部分的な並べ替えを実行してから、部分的な並べ替えをマージします。
外部マージソートの手順
- n = 10億の乱数を取り、それらを同じサイズの20個の破片に分割します。
- 各シャードを小さいものから大きいものへと個別にソートし、それぞれを独自のファイルに書き込みます。
- 40 mmapを開き、各ファイルに2つ、前進用に1つ、後退用に1つ、ミューテックスを各ファイルに関連付けます。
std::multiset<T,LessThan> buff_fwd;順方向スレッド用にaをインスタンス化std::multiset<T,GreaterThan> buff_revし、逆方向スレッド用にaをインスタンス化します。ここで優先キューを使用することを好む人もいますが、基本的には、ソートオンインサートコンテナがここで機能します。- 私は2つのバッファーを表面と岩底と呼び、最終的な並べ替えにまだ追加されていない最小数と最大数を表します。
- n / 2が使い果たされるまでシャードからアイテムを追加し、もう一方のスレッドでmmapを使用して、シャードを最初から中央に向かって、最後から中央に向かってフラッシュします。基本的には自由にフラッシュできますが、どちらかのバッファがメモリを使いすぎる前に、少なくとも1つはフラッシュする必要があります。