第28章 たのしいソート5

 今回は、前回の qsort を使って構造体配列をソートをしてみます。その時、とっても困ることが起きるのです。


 では、今回の要点です。


 では、いってみましょう。


 前回と違い、今回は構造体のソートをします。その構造体は次のようなものにします。

struct SMember   // 会員データ
{
    int nID;     // ID
    int nYear;   // 誕生年
    int nMonth;  // 誕生月
    int nDay;    // 誕生日
};

 データは乱数で20個作って、生年月日をもとに昇順でソートしたいと思います。

 それでは、早速プログラムを作ってみましょう。

プログラム
// Sort7.cpp
#include <stdio.h>
#include <stdlib.h>

#define numof(array)  (sizeof (array) / sizeof (*array))

struct SMember   // 会員データ
{
    int nID;     // ID
    int nYear;   // 誕生年
    int nMonth;  // 誕生月
    int nDay;    // 誕生日
};

// データの作成
void MakeData(SMember* pmems, int nNumOf)
{
    int i;

    for(i = 0; i < nNumOf; i++)
    {
        pmems[i].nID    = 1 + i;
        pmems[i].nYear  = 1950 + rand() % 40;
        pmems[i].nMonth = 1 + rand() % 12;
        pmems[i].nDay   = 1 + rand() % 28;
    }
}

// データの表示
void DispData(SMember* pmems, int nNumOf)
{
    int i;

    for(i = 0; i < nNumOf; i++)
    {
        printf("会員No.%2d : %4d年 %2d月 %2d日 生まれ\n",
               pmems[i].nID,    pmems[i].nYear,
               pmems[i].nMonth, pmems[i].nDay);
    }
}

// データの比較(生年月日)
int CompDate(const void* pElem1, const void* pElem2)
{
    // 一旦変数に入れておくと、データが扱いやすいですね
    const SMember* pmem1 = (const SMember*)pElem1;
    const SMember* pmem2 = (const SMember*)pElem2;

    int nDiff;  // 両要素の差

    nDiff = pmem1->nYear - pmem2->nYear;
    if(nDiff != 0)
        return nDiff;

    nDiff = pmem1->nMonth - pmem2->nMonth;
    if(nDiff != 0)
        return nDiff;

    return pmem1->nDay - pmem2->nDay;
}

int main()
{
    SMember amem[20];

    MakeData(amem, numof(amem));
    qsort(amem, numof(amem), sizeof *amem, CompDate);
    DispData(amem, numof(amem));

    return 0;
}

会員No. 5 : 1951年  4月 22日 生まれ
会員No. 1 : 1951年 12月  7日 生まれ
会員No.15 : 1952年 10月  6日 生まれ
会員No. 8 : 1954年  3月 14日 生まれ
会員No.18 : 1954年 11月 26日 生まれ
会員No.11 : 1957年  7月 16日 生まれ
会員No. 6 : 1961年  8月 15日 生まれ
会員No. 9 : 1962年 11月  6日 生まれ
会員No.17 : 1963年  5月 12日 生まれ
会員No.14 : 1964年 12月 12日 生まれ
会員No.12 : 1968年 10月  5日 生まれ
会員No. 2 : 1970年  6月 17日 生まれ
会員No.20 : 1971年  2月 23日 生まれ
会員No. 4 : 1974年  6月  6日 生まれ
会員No.16 : 1974年 10月 12日 生まれ
会員No. 7 : 1977年  1月 24日 生まれ
会員No.13 : 1977年  8月 12日 生まれ
会員No.10 : 1986年  3月 16日 生まれ
会員No.19 : 1987年  8月 16日 生まれ
会員No. 3 : 1988年  7月 27日 生まれ

 はい、きちんとソートできましたね。


 と、ここまでは大したことはやっていません。強いて言えば、qsort の使い方のサンプルのようなものです。

 本題はこれからです。ここでもし、構造体のサイズを大きくし要素数を10万にするとどうなるでしょうか? ちょっと試してみましょう。

プログラム
// Sort7b.cpp
#include <stdio.h>
#include <stdlib.h>

struct SMember   // 会員データ
{
    int nID;     // ID
    int nYear;   // 誕生年
    int nMonth;  // 誕生月
    int nDay;    // 誕生日
    int dummy[124];  // ダミーデータ
};

// データの作成
void MakeData(SMember* pmems, int nNumOf)
{
    int i;

    for(i = 0; i < nNumOf; i++)
    {
        pmems[i].nID    = 1 + i;
        pmems[i].nYear  = 1950 + rand() % 40;
        pmems[i].nMonth = 1 + rand() % 12;
        pmems[i].nDay   = 1 + rand() % 28;
    }
}

// データの比較(生年月日)
int CompDate(const void* pElem1, const void* pElem2)
{
    const SMember* pmem1 = (const SMember*)pElem1;
    const SMember* pmem2 = (const SMember*)pElem2;

    int nDiff;  // 両要素の差

    nDiff = pmem1->nYear - pmem2->nYear;
    if(nDiff != 0)
        return nDiff;

    nDiff = pmem1->nMonth - pmem2->nMonth;
    if(nDiff != 0)
        return nDiff;

    return pmem1->nDay - pmem2->nDay;
}

int main()
{
    SMember*  pmem;
    const int nNumOf = 100000;

    // 大きな配列は動的に確保する!
    pmem = new SMember[nNumOf];
    if(pmem == NULL)
        return 0;

    MakeData(pmem, nNumOf);
    qsort(pmem, nNumOf, sizeof *pmem, CompDate);

    delete [] pmem;

    return 0;
}

 この qsort の実行速度を測ってみたところ、20回平均で6.8秒(MMXペンティアム300MHzで測定)でした。前回、10万要素の int 型配列のソートは0.3秒程度と言いました。構造体だと何故これほどまでに遅くなるのでしょうか?

 これは、構造体の交換に時間がかかるからです。今回の構造体のサイズは512バイトです。512バイトのデータ2つを交換するのは、4バイトのデータ2つを交換するよりも時間がかかるのは当然ですね。

 となると、大きな構造体のソートには非常に時間がかかるということになります。しかし、ソートの対象は構造体であることが多く、それではとても不便です。では、どのようにすればいいのでしょうか?

 そこで、構造体をポインタを介して使うようにします。どういうことかというと、もともとの構造体を直接ソートするのではなく、各要素へのポインタの配列を用意し、そのポインタをソートすればいい、ということです。

 イメージしづらいかもしれませんね。ということで、図を用意してみました。

間接ソート
図.1 間接ソート

 先ず、元の配列があって、その各要素へのポインタを持つ配列をもう1つ用意します。ポインタは、同じ色の要素のアドレスを持っていると考えて下さい。

 そして、ソートはこのポインタ配列をソートします。といっても、ポインタに入っているアドレスを比較してソートするのではなく、その参照先のデータを比較してソートします。

 で、一番下の配列がソートされた配列です。色をたどってみるとソートされていることが分かりますね。

 そしてもちろんのことですが、元の配列はソートされていないので、データを扱う際にはソートしたポインタを通す必要があります


 では、プログラムを作ってみましょう。

プログラム
// Sort7c.cpp
#include <stdio.h>
#include <stdlib.h>

struct SMember   // 会員データ
{
    int nID;     // ID
    int nYear;   // 誕生年
    int nMonth;  // 誕生月
    int nDay;    // 誕生日
    int dummy[124];  // ダミーデータ
};

// データの作成
void MakeData(SMember* pmems, int nNumOf)
{
    int i;

    for(i = 0; i < nNumOf; i++)
    {
        pmems[i].nID    = 1 + i;
        pmems[i].nYear  = 1950 + rand() % 40;
        pmems[i].nMonth = 1 + rand() % 12;
        pmems[i].nDay   = 1 + rand() % 28;
    }
}

// アドレスのセット
void SetAddresses(SMember** ppmem,
                  const SMember* pmemMaster, int nNumOf)
{
    int i;
    for(i = 0; i < nNumOf; i++)
        ppmem[i] = &pmemMaster[i];
}

// データの比較(生年月日)
int CompDate(const void* pElem1, const void* pElem2)
{
    // pElem1 はポインタ(渡した配列の要素)へのポインタ
    const SMember* pmem1 = *(const SMember**)pElem1;
    const SMember* pmem2 = *(const SMember**)pElem2;

    int nDiff;  // 両要素の差

    nDiff = pmem1->nYear - pmem2->nYear;
    if(nDiff != 0)
        return nDiff;

    nDiff = pmem1->nMonth - pmem2->nMonth;
    if(nDiff != 0)
        return nDiff;

    return pmem1->nDay - pmem2->nDay;
}

int main()
{
    SMember*  pmemMaster;  // 元の配列
    SMember** ppmem;       // 実際に使う配列(ポインタの配列)
    const int nNumOf = 100000;

    pmemMaster = new SMember[nNumOf];
    if(pmemMaster == NULL)
        goto ALLOC_ERROR1;

    ppmem = new SMember*[nNumOf];
    if(ppmem == NULL)
        goto ALLOC_ERROR2;

    MakeData(pmemMaster, nNumOf);
    SetAddresses(ppmem, pmemMaster, nNumOf);
    qsort(ppmem, nNumOf, sizeof *ppmem, CompDate);

    delete [] ppmem;
ALLOC_ERROR2:
    delete [] pmem;
ALLOC_ERROR1:
    return 0;
}

 ポインタでソートした時の時間は20回平均で1.2秒でした。要素への参照が1段階増える分比較に若干時間がかかりますが、それでもソート時間は約4分の1に短縮されています。

 このように、要素数の多い構造体のソートはポインタを介してソートするとかなり速くなります。活用しましょう。

 そして重ねて言いますが、実際に構造体のデータを使うときには、そのポインタを介して要素を扱わないとソートはされていないという点に注意して下さい。


 それでは、今回の要点です。


 次回はさらに新しいソート法を話します。限定的にしか使えませんが非常に高速です。


第27章 たのしいソート4

Last update was done on 2000.9.22

この講座の著作権はロベールが保有しています