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

データの並び替え(4)[2012.12.11]
浮動小数点配列の並び替え(または構造体配列の浮動小数点型要素の並び替え)について記す。

1.qsort関数を使用する

やはりライブラリ関数qsortを使うのが一番簡単である。

コールバック関数は、整数値を返却値としなければならないのが、注意点である。

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

void print_array(double array[], int size) {
    int i;
    for (i = 0; i < size; i++) {
        printf("%.1f ", array[i]);
    }
    printf("\n\n");
}

int cmp(const void *a, const void *b) {
   return (int)((*((double*)a) - *((double*)b))*10.0);
}
int main() {
    int n;
    int ARRAY_SIZE = 500000;

    double *data = calloc(ARRAY_SIZE, sizeof(double));
    for (n = 0; n < ARRAY_SIZE; n++)
	data[n] = rand()/10.0;
    print_array(data, ARRAY_SIZE);      /* ソート前の配列を出力 */
    qsort(data, ARRAY_SIZE, sizeof(double), cmp);  /* クイックソート実行   */
    print_array(data, ARRAY_SIZE);      /* ソート後の配列を出力 */
}

上のプログラムでは、小数点以下1桁の精度であり、10倍した値を int型にキャストしてもオーバフローを起こさないことを前提としたコールバック関数を用いている。

そもそも、このような前提が可能ならば、浮動小数点配列ではなく、 値を10倍し整数配列とした方が並び替え時間も速くなる。

一般的には、このような前提のない比較関数を用いる必要がある。一例を下に示す。

int cmp(const void *a, const void *b) {
    double v = *((double*)a) - *((double*)b);
    return v > 0.0 ? 1 : v == 0.0 ? 0 : -1;
}

並び替えに要する時間はこの比較関数に大きく依存する。 どのような比較関数が最も高速になるかは、コンパイラや実行マシンに依存するので、 上のプログラムがベストとは限らない。

実行時間を問題にするならば、 qsort関数に当たる関数を実装し、コールバック関数コールのオーバヘッドを無くすべきであろう。 究極の高速化を目指すならば、局所的にはインライン・アセンブラの使用も有効となろう。

個人使用で実行時間の短縮を望むのは、殆どの場合、CPU時間でなく、I/O時間である。 昔は、一、二度インライン・アセンブラを使ったような気もするが、近年は全く経験がない。