単連結リストの整列 #92 バケツソートによる基数ソートにかかる時間
非比較整列法であるバケツソートを利用した基数ソートでは、
整列にどれくらいの時間がかかるのか計測してみる。
#include <stdio.h> #include <stdlib.h> #include <assert.h> #include <time.h> #include "intlist.h" static intlist_t rsort(intlist_t list, int n) { int i, s; intlist_t bucket[16], prev_list = list; for (i = 0, s = 0; i < n; i++, s += 4) { int k; intiter_t iter; intlist_t next_list = intlist_new(); for (k = 0; k < 16; k++) bucket[k] = intlist_new(); iter = intlist_iterator(prev_list); while (intiter_has_next(iter)) { int v = intelem_get_val(intiter_next(iter)); intlist_add_first(bucket[((unsigned int)v >> s) & (16 - 1)], v); } intiter_dispose(iter); for (k = 16 - 1; k >= 0; k--) { intiter_t it = intlist_iterator(bucket[k]); while (intiter_has_next(it)) { intlist_add_first(next_list, intelem_get_val(intiter_next(it))); } intiter_dispose(it); } if (prev_list != list) intlist_dispose(prev_list); prev_list = next_list; for (k = 0; k < 16; k++) intlist_dispose(bucket[k]); } return prev_list; } static int nstep(void) { int i, n = 0; for (i = RAND_MAX; i != 0; i /= 16) n++; return n; } static void check(intlist_t list) { int pv; intiter_t i = intlist_iterator(list); if (intiter_has_next(i)) { pv = intelem_get_val(intiter_next(i)); while (intiter_has_next(i)) { int v = intelem_get_val(intiter_next(i)); assert(pv <= v); pv = v; } } intiter_dispose(i); } #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, rand()); } return list; } #ifdef NOSORT #define DOSORT 0 #else #define DOSORT 1 #endif #ifdef NORSORT #define DORSORT 0 #else #define DORSORT 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]; const int ns = nstep(); int k; srand(54321); puts("# nelems elapsed"); for (k = 0; k < nkind; k++) { clock_t s, e; int i; s = clock(); for (i = ntrials[k]; i > 0; i--) { intlist_t list = make_list(nelems[k]); if (DOSORT) { if (DORSORT) { intlist_t sorted = rsort(list, ns); check(sorted); intlist_dispose(sorted); } else { intlist_sort(list, issup, NULL); check(list); } } intlist_dispose(list); } e = clock(); printf("%d %.1f\n", nelems[k], (double)(e - s) / CLOCKS_PER_SEC * 1000 / ntrials[k] * 100); /* average time [ms] per a batch of 100 trials */ } return 0; }
計測プログラムは以前から利用しているものを流用している。
ただし、基数ソートはintlist_sort関数を呼び出す形になっていないので、
整列関数rsortの呼び出しに変更している。
基数ソートでは比較回数等は意味を持たないので割愛している。
マクロ定数NORSORTをコンパイル時に与えることで、
これまで通りのintlist_sort関数による整列も行えるようにした。
また、整列済みのリストが正しく整列されていることをチェックする関数checkで確認している。
チェックする分、処理時間はもちろん長くなるが、
rsortでもintlist_sortでも正しく整列されていれば同じだけの時間がチェックにかかる。
しかもチェック処理は要素数の一次オーダの時間計算量であるので、
一次オーダかそれ以上以上の時間計算量が他の処理に必要なのであれば、
時間計算量の概算を求めるのには多分影響してこないだろう。
実行結果は以下の通り。
リスト中の要素数と、整列の所要時間をリスト100個当たりの平均処理時間換算（ミリ秒）で出力している。
まず、単連結リストを隣接交換法で実装したintlist_sortによって整列した。
# nelems elapsed 200 307.3 300 992.2 400 2333.3 600 7640.6 800 17854.2 1200 59250.0 1600 140791.7
次に、双方向連結リストを同じintlist_sortで整列したもの。
# nelems elapsed 200 36.5 300 93.8 400 177.1 600 375.0 800 666.7 1200 1562.5 1600 2708.3
そして、単連結リストを基数ソートrsortで整列した場合。
# nelems elapsed 200 15.6 300 23.4 400 41.7 600 46.9 800 83.3 1200 125.0 1600 166.7
最後に、双方向連結リストをrsortで整列した結果である。
# nelems elapsed 200 20.8 300 23.4 400 31.2 600 62.5 800 83.3 1200 125.0 1600 166.7
