トップC-Tips > データの並び替え(3)

データの並び替え(3)[2012.11.08]
データの並び替えの高速化に関わる話をもう一つ続けよう。視点が異なるので、ページを改める。 業務ソフトでは同じような特徴を持ったデータを頻繁に並び替えるケースがある。 並び替えに要する時間が問題にならない場合には、qsort関数を使えばよい。 しかし、高速化を求められるときには、並び替えるデータによっては、 qsort関数を使うよりも、大幅に高速化を図れるケースがある。

1.バケット・ソート

ランダムな並びのデータの並び替えアルゴリズムとしては、クイックソートが著名である。

実は、"ランダム"のほかに、"重複が少なく"、"余分なメモリ領域を使いたくない" ときには 高速という但し書きがつく。

試験の点数、年齢、住所(番地までは含まない)などで並び替えるときには、 多くの重複がある。一般に、大量のデータでは重複するデータが多いのが普通である。 この重複の度合いが大きいときには、クイック・ソートよりもはるかに高速に並び替える方法がある。 そのひとつが、バケット・ソートまたはバケツ・ソートである。

例えば、試験の成績を点数順に並び替える場合、 0点から100点まで合計101個の点数別のトレイ(バケツ)を用意しておき、 点数に応じて、該当するトレイ(バケツ)にポン、ポンと入れてゆくものである。

これをコンピュータで実行する場合には、 例えば、サイズ(容量)がいくらでも増やせる可変長配列を使うことになる。

しかし、毎回、サイズをチェックしなければならない。このチェック時間が無視できない。 別の方法として、1回目は、同じ点数がそれぞれいくつあるかだけを調べ、 元のデータ配列のサイズと同じだけの配列を用意して、入れる場所を0点から順に、 それぞれの個数分割り当てる。そして、2回目に、そこにコピーしてゆく。 このプログラムを下に示す。 アルゴリズムはクイックソートよりはるかにシンプルであるが、余分にメモリがいる。

2.qsort関数によるソート時間の確認

まず、次のプログラムで、値の範囲を 0〜100 としたときの qsort関数によるソート時間を計測した。 いつの場合でも、実行時間はキャッシュ・メモリの影響などによりばらつくが、 50万データの並び替え時間のソート最低値は 0.109 秒となり、 重複が殆ど無いケースよりも、約3倍高速となった。

データ数を100万に増やした場合、0.234秒となった。

sort31.c

3.バケット・ソートによるソート時間の計測

sort32.c

ソート時間は0.047秒となり、qsort関数を使う場合に比べて、およそ5倍の速さとなった。

なお、MAX_VALUEを 1000000 として、重複を殆どなくした場合のソート時間は約0.4秒となった。 重複が少ないときは、バケット・ソートはクイック・ソートよりも遅くなる。

4.構造体配列のバケット・ソート

sort32.cで ARRAY_SIZE の値を 100 に変え、ソート前とソート後の整数配列を表示すると、 次のようになる。

c:\mh\www\c-tips\data-structure>sort33
 77  67  40  70  89  97  38  38  87  69   8  77  95  99   3  93  19   0  77  64
 76  80   0  73  65  30  14  93  55  75  62  84  92  51   2  86   6  25  95  24
  3  86  45  24  22  98  18  10  53  24   3  19  99   6  68  56  18  94  48  97
 82   1  56  99  61   6  52  61  76  64   6  59  48  14  74  60  40  25  69  55
 56  16  87  26  12  19  76  45  99  33  82  49  47  85   2  36  87 100  53   4

データ数: 100 実行時間: 0ミリ秒
  0   0   1   2   2   3   3   3   4   6   6   6   6   8  10  12  14  14  16  18
 18  19  19  19  22  24  24  24  25  25  26  30  33  36  38  38  40  40  45  45
 47  48  48  49  51  52  53  53  55  55  56  56  56  59  60  61  61  62  64  64
 65  67  68  69  69  70  73  74  75  76  76  76  77  77  77  80  82  82  84  85
 86  86  87  87  87  89  92  93  93  94  95  95  97  97  98  99  99  99  99 100

実は、このような並び替え後の結果を得るだけならば、dest配列もoffset配列も要らず、 count配列の値を求めるだけでよいので、 プログラムは簡単になり、実行時間も短縮される。

下のプログラムにより、上と同じ表示結果が得られる。

sort34.c

ARRAY_SIZE を 1000000 にした時の実行時間は 0.016秒に短縮される。

しかし、実用プログラムでは、整数配列の並び替えは少なく、 構造体配列の並び替えが多いと考えられる。 例えば、次のような構造体Studentの配列dataがあり、 それを成績(score)順に並び替えるといった形が普通である。

このような場合、dest配列には、値(成績)ではなく、 data配列上の何番目のデータかというインデックス(添え字)を格納する。 これによって、成績順に名前nameと成績scoreの値が表示できるようになる。 並び替え関数bucketSortは sort32.c と基本的に同じ形である。 このため、バケット・ソートは sort34.c ではなく、 sort32.c で評価する方が妥当と言える。

typedef struct _Student {
    char *name;
    int  score;		// 点数 0〜100
} Student;

#define ARRAY_SIZE  1000000
Student data[ARRAY_SIZE];       // 元のデータ配列
int dest[ARRAY_SIZE];           // 並び替えたインデックス配列
#define MAX_VALUE  100
int count[MAX_VALUE+1];         // 個数
int offset[MAX_VALUE+1];        // 先頭位置
// 中略
void bucketSort() {
    int i;
 
    // 出現回数を数える
    for (i = 0; i < ARRAY_SIZE; i++)
        count[data[i].score]++;
    // 開始位置計算
    offset[0] = 0;
    for (i = 0; i < MAX_VALUE; i++)
        offset[i+1] = offset[i] + count[i];
    // ソート処理 
    for (i = 0; i < ARRAY_SIZE; i++) {
        int target = data[i].score;
        int off = offset[target];
        dest[off] = i;
        offset[target]++;
    }
}
// 後略