今回は、前回の 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に短縮されています。
このように、要素数の多い構造体のソートはポインタを介してソートするとかなり速くなります。活用しましょう。
そして重ねて言いますが、実際に構造体のデータを使うときには、そのポインタを介して要素を扱わないとソートはされていないという点に注意して下さい。
それでは、今回の要点です。
次回はさらに新しいソート法を話します。限定的にしか使えませんが非常に高速です。
Last update was done on 2000.9.22
この講座の著作権はロベールが保有しています