構造体の配列があります
struct
{
string name;
string 2nd_name;
int age; // 0 to 150
}
配列の最大長は 10^8 です。
マージソート/クイックソートおよび他のすべてのよく知られたアルゴリズムを使用できることはわかっていますが、ソートを高速化する何かを追加できるかどうか知りたいです。
質問する
1160 次
2 に答える
6
人々の年齢は、並べ替えの任意の整数とは多少異なります。可能な個別の値の数は非常に少ないです（すべての人々の年齢は0から150の間です）。したがって、並べ替える最も簡単な方法は、151個のリンクリスト（バケットと呼びましょう）を割り当て、年齢に応じて各人のデータ構造をバケットに入れることです。
bucket[person->age].add(person)
于 2012-10-28T14:34:13.997 に答える
4
まず、構造体が非常に大きい（つまり長い名前）場合でも、ファイルシステムの並べ替えを使用する必要はありませんが、メモリ内の並べ替えを使用できることに注意してください。
# elements * 8 ~= 762 MB (most modern systems have enough memory for that)
^
key(age) + pointer to struct requires 8 bytes in 32 bits system
ディスクアクセスはランダムアクセスではなく、ディスクアクセスはRAMアクセスよりもはるかに遅いため、ディスクアクセスを最小限に抑えることが重要です。
ここで、その上で任意の種類を使用します。並べ替えプロセスにディスクを使用することは避けてください。
この場合の（RAM上の）ソートのいくつかの可能性は次のとおりです。
- 標準のクイックソートまたはマージソート
- 怒りは[0,150]に制限されているため、バケットソートもここで適用できます。
- 基数ソート（同じ理由で、基数ソートにはceil（log_2（150））〜=8回の反復が必要です。
于 2012-10-28T14:34:30.530 に答える