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

データの並び替え(2)[2012.11.07]
データの並び替えは通常は標準ライブラリ関数qsortを使えばよい。 何らかの理由で少しでも高速化を図りたい場合には、自前で並び替え関数を作る方法がある。

1.qsort関数による整数配列の並び替え

データの並び替えはライブラリ関数qsortを用いるのが一番簡単である。 データ配列要素の比較結果を返すコールバック関数を記述するだけでよい。

下に、整数配列を小さい順に並び替えるプログラムを示す。

sort21.c

50万要素の整数配列の並び替えに要する時間は 0.312 秒となった。

通常はこの方法で十分であるが、 何らかの理由で少しでも高速化を計りたい場合には、多少問題がある。 比較関数は通常はシンプルなプログラムである。 このような場合、比較関数呼び出しのオーバヘッドが処理時間全体に占める比重が高い。

2.コールバック関数の使用をやめる

ソート・アルゴリズムとしてはいくつかの方法が知られているが、 ランダムなデータの並び替えにクイック・ソートが最も高速なことが知られている。

ソート・アルゴリズムとしては難しい方に分類されるが、 プログラム自体は比較的小さい。

sort22.c

このプログラムでは、データの比較をコールバック関数で行わず、 pivot関数、partition関数内部で直接比較しているため、オーバヘッドが少ない。

50万要素の整数配列の並び替えに要する時間は 0.203 秒となった。

3.並び替え時間の短縮

一般的にはクイックソートが一番高速であるが、更に並び替え時間を短縮する方法がよく知られている。

単純なソートアルゴリズムとして、 下のプログラムに示すような選択ソートおよび挿入ソートがある。 配列要素のサイズが大きい時は並び替えに時間がかかりすぎるが、 サイズが小さい時は、クイックソートなどの高度なアルゴリズムよりも速いという特徴がある。

クリックソートは部分配列の並び替えを繰り返し、全体の配列の並び替えを行うが、 この部分配列のサイズが小さくなったら、 選択ソートまたは挿入ソートで並び替える方が高速になる。

sort23.c

上のプログラムでは、部分配列のサイズが10以下となったとき、選択ソートで並び替えを行っている。 この結果、50万要素の整数配列の並び替えに要する時間は 0.187秒に短縮された。

ここで使用している qsort関数はWindowsパソコンに標準装備の msvcrt.dll に含まれるものである。 このプログラムのソースを調べた訳ではないが、上で述べたような方法を採用している可能性がある。

こう考えると、0.187秒から0.312秒への増加分の殆どがコールバック関数の呼び出しのオーバヘッドである。

4.関数呼び出しのオーバヘッド

sort21.exe からコールバック関数cmpに対応する機械語プログラムを抜き出したものを以下に示す。 最初の2行と最後の2行が関数呼び出しのオーバヘッドである。 このほか、qsort関数には、二つの引数をスタックに積み、cmp関数をコールし、 戻った後、スタックポインタを元に戻すオーバヘッドがある。 即ち、オーバヘッドとなる命令数が全体で約10命令に及ぶのにたいして、 実際の演算を行う命令は5命令に過ぎない。

並び替えアルゴリズムでは、頻繁にデータの比較が行われるため、 データ比較時間が全体の処理時間に占める比重はたかい。 従って、関数呼び出しのオーバヘッドが全体に占める比重が極めて高くなる。

00401048 55                     push    ebp
00401049 89E5                   mov     ebp,esp
0040104B 8B4508                 mov     eax,[ebp+8]
0040104E 8B00                   mov     eax,[eax]
00401050 8B4D0C                 mov     ecx,[ebp+0Ch]
00401053 8B09                   mov     ecx,[ecx]
00401055 2BC1                   sub     eax,ecx
00401057 C9                     leave
00401058 C3                     ret

関数呼び出しのオーバヘッドが大きいことは 別のページでも示している。 フィボナッチ数列を再帰関数呼び出しで30番目まで求めるのに、46ミリ秒かかっている。 関数呼び出しを使わない方法では、0.0002〜0.0003ミリ秒しかかからない。

関数化は分かりよいが、呼び出し回数が頻繁な時には注意が必要である。