単連結リストの整列 #56 時間的性能の変化の程度

実際の整列処理においてはどの程度時間的性能が変化しているのか確かめてみた。
次のような計測プログラムを書いた。

test_ilist2_2.c

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

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

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

int main(void)
{
    clock_t s, e;
    srand(7654321);
    iinit();
    s = clock();
    isort(issup, NULL);
    e = clock();
    printf("%.3f\n", (double)(e - s) / CLOCKS_PER_SEC);
    return 0;
}

コンパイラオプション-DNELEM=1000を指定してilist2.cの変更前後それぞれのオブジェクトファイルを作成し、
上の計測プログラムにlistsort.cとともにリンクして、それぞれ実行した。
関数prevが使われている変更前のilist2の場合、

$ ./test_ilist2_2
0.843

だったが、関数prev2に変更した後のilist2を使うと、

$ ./test_ilist2_2
0.671

となり、変更後の実行時間は変更前の8割程度になった。
実行時間の平均的な短縮の度合いはサンプルを多く取らなければ何もいえないが、
1000個の要素全ての値が異なる場合の要素の交換回数に比べると、
実際の要素の値の種類が90種類しかないことでその交換回数が随分少ないであろうことを考えると、
それでも2割の短縮になっていることから、この変更は多分それなりに効果があるものなのだろうとは思う。