ロベールのＣ＋＋教室 - 第２８章たのしいソート５ -

第２８章　たのしいソート５

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

　では、今回の要点です。

構造体の配列を直接ソートすると遅い。
要素へのポインタ配列を作り、そのポインタをソートするとよい。

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

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

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

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

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

プログラム
// Sort7.cpp #include <stdio.h> #include <stdlib.h> #define numof(array) (sizeof (array) / sizeof (array)) struct SMember // 会員データ { int nID; // ＩＤ 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日生まれ

プログラム

// Sort7.cpp
#include <stdio.h>
#include <stdlib.h>

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

struct SMember   // 会員データ
{
    int nID;     // ＩＤ
    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 の使い方のサンプルのようなものです。

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

プログラム
// Sort7b.cpp #include <stdio.h> #include <stdlib.h> struct SMember // 会員データ { int nID; // ＩＤ 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; }

プログラム

// Sort7b.cpp
#include <stdio.h>
#include <stdlib.h>

struct SMember   // 会員データ
{
    int nID;     // ＩＤ
    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 の実行速度を測ってみたところ、２０回平均で６．８秒（ＭＭＸペンティアム３００ＭＨｚで測定）でした。前回、１０万要素の int 型配列のソートは０．３秒程度と言いました。構造体だと何故これほどまでに遅くなるのでしょうか？

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

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

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

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

図．１　間接ソート

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

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

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

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

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

プログラム
// Sort7c.cpp #include <stdio.h> #include <stdlib.h> struct SMember // 会員データ { int nID; // ＩＤ 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; }

プログラム

// Sort7c.cpp
#include <stdio.h>
#include <stdlib.h>

struct SMember   // 会員データ
{
    int nID;     // ＩＤ
    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;
}

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

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

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

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

構造体の配列を直接ソートすると遅い。
要素へのポインタ配列を作り、そのポインタをソートするとよい。

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

第２７章　たのしいソート４

Last update was done on 2000.9.22

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