3

通常、構造体オブジェクトの配列の並べ替えは簡単です。構造体の配列（AOS）を考えてみましょう

#define ITEMS 10

typedef struct MyStruct
{
 char a;
 int  b;
}tMyStruct;

tMyStruct arr_mystruct[ITEMS];

まず、この構造体の配列に<a、b>ペアの値を入力します。

この構造体の配列を整数フィールドに従ってソートする場合は、2つの整数引数をとる比較関数を使用してlibcqsort関数を使用してソートできます。

ここで、上記のAOS形式の構造をSOA形式に置き換えることを検討してください。

#define ITEMS 10

typedef struct MyStruct
{
 char a[ITEMS];
 int  b[ITEMS];
}tMyStruct;

tMyStruct mystruct;

これで、qsortを使用して整数の配列bフィールドを並べ替えることができますが、今回は、bの並べ替え順序でa（文字の配列）を追加で並べ替える必要があります。

だから私の質問は、通常のAOS形式の代わりにSOA形式でレイアウトされたデータの並べ替えを行うための可能な効率的な方法は何ですか？

誰かがこれで私を助けることができますか？ありがとう！

4

2 に答える 2

0

おそらく最良の方法は、ヘルパー配列を使用することです。

int helper[ITEMS];

int helper_cmp(const void *a, const void *b);

for (i = 0; i < ITEMS; ++i)
    helper[i] = i;
qsort(helper, ITEMS, sizeof(*helper), helper_cmp);

このhelper_cmp関数は、helper値をインデックスとして受け取りmystruct.b、それらの値を比較します。

int helper_cmp(const void *a, const void *b)
{
    int first = *(const int *)a;
    int second = *(const int *)b;
    int b_first = mystruct.b[first];
    int b_second = mystruct.b[second];
    // compare b_first and b_second
}

次に、の後にqsort、ヘルパー配列にの再配置されたインデックスが含まれb、順序付けの方法が示されます。

この配列を使用して、との両方を再配置できmystruct.aますmystruct.b。

これは「構造体の配列」のソートほど効率的ではないことに注意してください。あなたのアプリケーションはわかりませんが、配列のフィールドが相関している「配列の構造体」は、そもそも良い考えではないと思います。つまり、並べ替えがの並べ替えにb影響を与える場合a、それらはおそらく同じ概念要素に属しており（必要に応じてクラスと呼びます）、1つにグループ化するとよいでしょうstruct。

于 2012-07-27T15:34:49.937 に答える
0

ヘルパーの提案以外に、qsort（）でこれを行う方法はありません。このような場合、私は独自のソート関数を作成します。速度と書きやすさの最適なバランスをとるために、挿入ソートは小さな配列でうまく機能し、マージソートは大きな配列でうまく機能することがわかりました。

于 2012-08-01T00:13:43.003 に答える