- [2-1]
- ここで、ベンチマーク結果を示したいと思います。・・・0から999999まで、数を数えて文字列にします。これで"0", "1", "2", "3", ... という100万件の文字列データができます。これをqsortでソートします。その際に比較関数を
int qscmp(const void *a, const void *b)
{
return strcmp(*(char **) a, *(char **) b);
}
- としてみました。すると当方の環境（Kano PC, Celeron N4000）では、初期の並びを配列に書き込んでqsort()が終わるまでに340ミリ秒かかりました。ソート結果を出力するとこうなっていました。
0
1
10
100
1000
10000
100000
100001
100002
100003
100004
100005
100006
100007
100008
100009
10001
100010
100011
- いい感じに混ざり合っているのがよくわかります。次に、比較関数を改良しました。strcmp()は遅いので、使わない形に書きました。
int qscmp(const void *a, const void *b)
{
const unsigned char *ca = *(const unsigned char **) a, *cb = *(const unsigned char **) b;
if (ca[0] != cb[0]) return ca[0] - cb[0];
if (ca[1] != cb[1]) return ca[1] - cb[1];
if (ca[2] != cb[2]) return ca[2] - cb[2];
if (ca[3] != cb[3]) return ca[3] - cb[3];
if (ca[4] != cb[4]) return ca[4] - cb[4];
if (ca[5] != cb[5]) return ca[5] - cb[5];
return ca[6] - cb[6];
}
- こうすると、286ミリ秒になりました。もちろん結果は同じです。ではもっと改良します。32bitのintを使って、4文字ずつ比較します。
int qscmp(const void *a, const void *b)
{
const unsigned int *ca = *(const unsigned int **) a, *cb = *(const unsigned int **) b;
if (ca[0] != cb[0]) return ca[0] - cb[0];
return ca[1] - cb[1];
}
- この比較を成功させるためには、文字列を加工する必要があります。x86はリトルエンディアンなので、char *s;のs[0]が上位に来てくれないのです。それでエンディアンを入れ替える処理を追加しました。するとソートに要する時間は278ミリ秒になりました（このキーの加工にかかる時間はこの278ミリ秒には含まれません）。32ビット環境ではこれくらいがqsort()での限界かなと思います。
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
