単連結リストの整列 #71 所要時間の実測

C

整列に要する時間を実測して整列処理の時間計算量に関して考えてみる。

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

#define UNUSED_ARG(x) (void)(x)

static int issup(cintelem_t p, cintelem_t q, void *arg)
{
    UNUSED_ARG(arg);
    return intelem_get_val(p) > intelem_get_val(q);
}

static intlist_t make_list(int size)
{
    int i;
    intlist_t list = NULL;
    if (size >= 0 && (list = intlist_new()) != NULL) for (i = 0; i < size; i++) {
        intlist_add_first(list, (int)((unsigned)rand() << 16 | (unsigned)rand()));
    }
    return list;
}

#ifdef NOSORT
#define DOSORT 0
#else
#define DOSORT 1
#endif

int main(void)
{
    const int nelems[] = {200, 300, 400, 600, 800, 1200, 1600};
    const int ntrials[] = {192, 128, 96, 64, 48, 32, 24};
    const int nkind = sizeof nelems / sizeof nelems[0];
    int k;
    srand(54321);
    puts("# nelems ncmps nswps elapsed");
    for (k = 0; k < nkind; k++) {
        clock_t s, e;
        unsigned long ncmps = 0, nswps = 0;
        int i;
        s = clock();
        for (i = ntrials[k]; i > 0; i--) {
            intlist_t list = make_list(nelems[k]);
            if (DOSORT) intlist_sort(list, issup, NULL);
            ncmps += intlist_get_compare_counts(list);
            nswps += intlist_get_swap_counts(list);
            intlist_dispose(list);
        }
        e = clock();
        printf("%d %.1f %.1f %.1f\n",
            nelems[k],
            (double)ncmps / ntrials[k], (double)nswps / ntrials[k], /* average counts of #comparisons, #swaps per 1 trial */
            (double)(e - s) / CLOCKS_PER_SEC * 1000 / ntrials[k] * 100); /* average time [ms] per a batch of 100 trials */
    }
    return 0;
}

ランダムな整数値をもつ要素数nelems[]個のリストのntrials[]セットについて、
整列処理での比較回数と交換回数、および実行時間の平均値について測定する。
linux上で実行しているのでclock関数の戻り値の差は処理に要したCPU時間を測定することになる。

まず、コンパイル時にNOSORTマクロを定義して整列処理を含まない場合についてみてみると、

# nelems ncmps nswps elapsed
200 0.0 0.0 0.0
300 0.0 0.0 0.0
400 0.0 0.0 0.0
600 0.0 0.0 0.0
800 0.0 0.0 0.0
1200 0.0 0.0 0.0
1600 0.0 0.0 0.0

結果のフィールドはそれぞれ左から要素数、1セット当たりの比較回数の平均、
1セット当たりの交換回数の平均、100セット当たりに換算した実行に要する平均CPU時間（ミリ秒）である。
整列処理は行っていないので比較と交換回数は当然0である。
また、処理時間も無視できるとしていいだろう。
もし、目に見えるほどに時間がかかるならそれは要素数の一次オーダでおさえられるはずである。

次に、整列処理を行わせてみる。

# nelems ncmps nswps elapsed
200 19759.3 9878.0 296.9
300 44613.6 22434.0 984.4
400 79462.8 40089.3 2229.2
600 179024.9 89819.1 7296.9
800 318956.3 159787.6 17166.7
1200 718483.7 358853.3 57312.5
1600 1277827.0 642036.1 135333.3

要素数200, 400, 800, 1600の系列、要素数300, 600, 1200の系列ともに、
すごくおおざっぱにみて、比較回数と交換回数は4倍ずつ、CPU時間は8倍ずつ増加している。
また隣り合う要素数間では比較と交換回数が2倍、CPU時間が3倍になっているようにみえる。
比較回数と交換回数が要素数の二次オーダ、処理時間が三次オーダになるだろうという前回の話に合った結果である。