ソートの計算量と現実のプログラム

ソートアルゴリズムについての小ネタ。「ソートは迷わずクイックソート」と言われることがよくありますが^[1]、場合によってはそれが最適ではないこともあるという話。ここではクイックソートと挿入ソートを比較します。

O-記法で書くとクイックソートの計算量はオーダーはO(n*log(n))で、単純な挿入ソートのそれはO(n^2)なので、見かけ上は前者のほうが速そうなのです。ただし、あくまでこの記法はnが無限に近づいたときの振舞いについて述べているだけなので、現実的なプログラムでは必ずしもクイックソートのほうが速いというわけではないです。

次のような仕様のプログラムで実際に両者の速度を比較してみましょう。

• 所定の下の整数要素を持つ配列をソートして、その所要時間出力する
• 第一引数(len): 要素数
• 第二引数(type): アルゴリズムの種類。'i'が挿入ソート。'q'がクイックソート。

この仕様を実装したのが以下のsortプログラムです。

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

#define NSECS_PER_MSEC 1000000UL
#define NSECS_PER_SEC 1000000000UL

static void insertion_sort(int *a, int len)
{
        int i, tmp;
        for (i = 1; i < len; i++) {
                tmp = a[i];
                if (a[i - 1] > tmp) {
                        int j;
                        j = i;
                        do {
                                a[j] = a[j - 1];
                                j--;
                        } while (j > 0 && a[j - 1] > tmp);
                        a[j] = tmp;
                }
        }
}

static inline long diff_nsec(struct timespec before, struct timespec after)
{
        return ((after.tv_sec * NSECS_PER_SEC + after.tv_nsec)
                - (before.tv_sec * NSECS_PER_SEC + before.tv_nsec));

}

static void prepare_data(int *a, int len)
{
        int i;
        for (i = 0; i < len; i++)
                a[i] = rand();
}

static int comp(const void *a, const void *b)
{
        return *((int *)a) - *((int *)b);
}

static char *progname;

int main(int argc, char *argv[])
{
        progname = argv[0];

        if (argc < 3) {
                fprintf(stderr, "usage: %s <len> <i|q>\n", progname);
                exit(EXIT_FAILURE);
        }

        int len = atoi(argv[1]);

        char type = argv[2][0];

        if (!((type == 'i') || (type == 'q'))) {
                fprintf(stderr, "%s: type should be 'i or q'\n", progname);
                exit(EXIT_FAILURE);
        }

        int *a;
        a = malloc(len * sizeof(int));
        prepare_data(a, len);

        struct timespec before, after;
        if (type == 'i') {
                clock_gettime(CLOCK_MONOTONIC, &before);
                insertion_sort(a, len);
                clock_gettime(CLOCK_MONOTONIC, &after);
        } else {
                clock_gettime(CLOCK_MONOTONIC, &before);
                qsort(a, len, sizeof(int), comp);
                clock_gettime(CLOCK_MONOTONIC, &after);
        }

        printf("%lu\n", diff_nsec(before, after));

        exit(EXIT_SUCCESS);
}

ビルド方法は次の通り。

$ CFLAGS=-O3 make sort
$ 

このプログラムを次のようなパラメタを使って実行しました。

パラメタ	値
第一引数(len)	2^(0, 1, 2, ..., 15)
第二引数(type)	i, q

結果を以下のグラフにプロットしました。x軸は2^(len)、y軸はlog(所要時間)なのに注意してください。

[f:id:satoru_takeuchi:20200329053129p:plain]

lenが大きくなっていくと確かにクイックソートのほうが速くなってゆき、その差は大きくなるばかりです。しかしlenが小さいとき、ここでは2^8(=128)あたりまでは挿入ソートのほうが速いことがわかります。これはクイックソートのほうが挿入ソートに比べて複雑な処理をしているためです。したがって、通常はクイックソートを使っていれば悪いようにはなりませんが、プログラムをカリカリにチューニングしたいとき、かつ、lenがそれほど大きくならないとわかっているときは挿入ソートを使って高速化に挑戦してみるのも一つの手です。ただし、「早すぎる最適化」という言葉にもある通り、最初からこの手の細かいチューニングをする必要はないでしょう。

最後に一点。上記のような理由もあって、本記事で作成したプログラムでも使っているglibcのqsort()関数は、ある程度小さなlen(<=MAX_THRESH)に対しては内部的に挿入ソートを使っています。他にもこのような実装になっている実装は山ほどあります。興味のあるかたは色々なクイックソートの実装を見てみるとよいでしょう。

脚注

1. とくにスクリプト言語の場合はソートアルゴリズムを自分で選択することも少ないかもしれません