C言語標準ライブラリに含まれるqsortは、配列のソートを行ってくれる関数です。第一引数にソート対象の配列、第二引数に配列の要素数、第三引数一要素のサイズ、第四引数に比較関数、のように渡すことで、ソートを行ってくれます。ここで、第四引数に渡す比較関数をどのように書くかについてまとめてみます。

比較関数の仕様

int comp( const void* lhs, const void* rhs )のような関数を書く必要があります。ここで、返り値は、

lhsの方が小さい（より正確には、「配列の先頭に近い方に配置してほしい」）場合は、負の値
lhsとrhsが等しい場合は、0
lhsの方が大きい（より正確には、「配列の末尾に近い方に配置してほしい」）場合は、正の値

を返す必要があります。

C++におけるstd::sortの比較関数のように二値を返すのではなく、三値（以上）を返す必要がある点に注意します。

比較対象が`char`の場合

比較対象がcharの場合、うまい方法があります。例えば昇順にソートしたい場合、以下のように書けば、仕様を満たせます。

int comp( const void* lhs, const void* rhs ) {
    return *(char*)lhs - *(char*)rhs;
}

ここで、*(char*)lhsや*(char*)rhsはchar型ですが、算術演算のオペランドになっているため、int型に変換されてから演算が行われます。したがって、この計算でオーバーフローは発生せず、仕様通り「lhsの方が小さい時は負の値、等しければ0、lhsの方が大きい場合は正の値」を返すことになります。

比較対象が`int`の場合

比較対象がintの場合、先のような引き算を使った方法はうまくいきません。なぜなら、int同士の引き算の結果は、intに収まる保証がないためです。 long longなど、int型より大きい型を使えばよいと思うかもしれませんが、返り値をintに収める必要があるため、やはりうまくいきません。

※あまりにも絶対値の大きな値が来ないことが分かっている場合など、オーバーフローが発生しないことが確実な場合、引き算を使った方法を使っても安全です。

このような場合、以下のような分岐を用いた比較関数を書くことが紹介されることがあります。

int comp( const void* lhs, const void* rhs ) {
    int L = *(int*)lhs;
    int R = *(int*)rhs;
    if( L < R ) { return -1; }
    if( L > R ) { return 1; }
    return 0;
}

しかし、これよりも以下のように書いたほうが高速です。

int comp( const void* lhs, const void* rhs ) {
    int L = *(int*)lhs;
    int R = *(int*)rhs;
    int lt = L < R;
    int gt = L > R;
    return gt - lt;
}

この書き方が高速な理由は、分岐がなくなっているからです。ソート関数中の分岐を先取りしているだけなので分岐予測ミスの回数自体は変わらなさそうに思いますが、実際には後者の方が分岐予測ミス数が少なくなります。これはソート関数中の分岐は非常に予測困難であることが関係しているのかもしれません。

測定

分岐を使って比較結果を返すのではなく、return (L > R) - (L < R);と書いたほうが速いのかを実際に確かめてみます。測定環境は以下です。

Ubuntu 20.04.4 LTS (WSL2 on Windows 11)
gcc 9.4.0、最適化オプションは-O3 -march=native
Intel Core i9 12900K (4880MHzくらいで動いている）

実験に用いたソースコードは以下です。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int comp( const void* lhs, const void* rhs ) {
  long L = *(long*)lhs;
  long R = *(long*)rhs;
  int gt = L > R;
  int lt = L < R;
  return gt - lt;
}

#define SIZE 100000000
long arr[SIZE];

int main() {
        for( int i = 0; i < SIZE; ++i ) {
                arr[i] = rand() + rand() * 0x100000000;
        }
        clock_t start = clock();

        qsort( arr, SIZE, sizeof(long), &comp );

        clock_t end = clock();

        printf( "Elapsed: %f\n", (double)(end - start) / CLOCKS_PER_SEC );
}

int comp( const void* lhs, const void* rhs ) {
  long L = *(long*)lhs;
  long R = *(long*)rhs;
  if (L > R) return 1;
  if (L < R) return -1;
  return 0;
}

測定の結果、前者は10.9±0.1秒程度でソートが終わりましたが、後者は11.3±0.1秒程度の時間がかかりました。このように、qsortに渡す比較関数中での分岐を減らすことは高速化につながることが分かります。

まとめ

charを比較するときには引き算を使うテクニックがある
int以上を比較したい場合には引き算のテクニックは使えない（オーバーフローするため）
オーバーフローを考慮に入れないといけない場合、(L > R) - (L < R)のように記述して分岐を減らす方が高速

よーる

qsortの比較関数の書き方について

比較関数の仕様

比較対象が`char`の場合

比較対象が`int`の場合

測定

まとめ

比較関数の仕様

比較対象がcharの場合

比較対象がintの場合

測定

まとめ

比較対象が`char`の場合

比較対象が`int`の場合