c - 非常に大きなファイルをmmapしてqsortを使用することは可能ですか?

Question

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

Answer 1

ファイルがアドレス空間の連続したマッピングに収まる場合は、これを行うことができます。そうでない場合は、できません。

違いについて：

• ファイルがほぼ収まる場合、さらにデータを追加すると、mmap は失敗します。もう少しデータがあるからといって、通常の外部ソートが突然停止することはありません。
• でマップしないとMAP_PRIVATE、ソートによって元のファイルが変更されます。通常の外部ソートは（必然的に）そうではありません
• でマッピングするとMAP_PRIVATE、VM にファイル全体を複製する余地がないと、いつでもクラッシュする可能性があります。繰り返しになりますが、厳密に外部ソートのメモリ要件は、データ サイズに比例してスケーリングしません。

---

tl;dr

可能性があり、予期せず回復不能に失敗する可能性があり、ほぼ確実に実行すべきではありません。

Answer 2

データがアドレス空間に収まる場合は間違いなく動作するはずです (64 ビット マシンではほぼ確実に動作します。32 ビット マシンでは動作する場合とそうでない場合があります) qsort。 . 考慮すべき問題の 1 つは、要素の数が膨大なのか、それとも各要素がディスク上で大きいのかということです。後者の場合は、 を実行したほうがよいでしょうが、mmap各要素に個別のポインター配列を割り当ててから、それらが指すものを比較する比較関数を使用してポインター配列を並べ替えます。これにより、データがメモリ内を移動する回数が大幅に減少しますが、出力を同じファイルに保存したい場合は、最後に少し手間がかかります。

Answer 3

はい、ファイルに固定長のレコードがあり、ファイルが連続した VM アドレスの範囲内に収まっている限り、これは可能です。実際、これは外部ソートに対する単純なアプローチと見なすことができます。ただし、qsort実装はこのユースケースに合わせて調整されていないため、町で最速のアルゴリズムではない可能性があります。