単連結リストの整列 #96 もっと要素数と試行回数を増やして計測

これまで比較による整列に遠慮していたので、
非比較による基数ソートのみで所要時間を計測して時間計算量をみてみる。

...snip
int main(void)
{
    const int nelems[] = {3162, 10000, 31623, 100000, 316228};
    const int ntrials[] = {2000, 632, 200, 63, 20};
...snip

このパラメータで単連結リストと双方向連結リストについて処理時間を計測した。
実行はUbuntu上である。

result3.dat

3162 288.5 328.5
10000 928.8 1061.7
31623 3055.0 3480.0
100000 15714.3 17142.9
316228 106800.0 113750.0

二種類の実行結果を扱いやすいように一つにまとめてある。
第一列目がリストの要素数、二列目が単連結リスト、三列目が双方向連結リストの整列に要する時間である。
要素数31623までは線形に処理時間が増えているようだが、
これ以上の要素数では時間の増加の仕方が増えているように見える。
gnuplotで、回帰分析すると、

f(x,a,b) = a * x + b
fit f(x,a1,b1) 'result3.dat' using (log($1)):(log($2)) via a1, b1
fit f(x,a2,b2) 'result3.dat' using (log($1)):(log($3)) via a2, b2

show variables a
show variables b

        Variables beginning with a:
        a1 = 1.27302338901343
        a2 = 1.25736190691999

        Variables beginning with b:
        b1 = -4.83774808470127
        b2 = -4.56669264728919

要素数に対する所要時間のスケーリング指数は1.2以上になっているが、
これは、

g(x,a,b) = exp(b) * x ** a

set key right bottom
set logscale xy
set pointsize 1.5
set xtics format "10^%L"
set xlabel "number of elements in a list"
set ytics format "10^%L"
set ylabel "elapsed time of 100 trials / ms"
plot [1000:1000000] [100:200000] \
  'result3.dat' using 1:2 title "single: elapsed", \
  'result3.dat' using 1:3 lc 3 title "double: elapsed", \
  g(x,a1,b1) lc 1 title sprintf("single: scaling exponent %.4g", a1), \
  g(x,a2,b2) lc 3 title sprintf("double: scaling exponent %.4g", a2)

で分かるように、要素数が多い領域で所要時間の増加傾向が大きくなっているためである。
これは基数ソートの本質的な部分というよりも、
リストの要素数が増えたことに伴う、その割り当てや解放にかかるコストではないかと考える。
リストの実装が要素一個一個を個別に大量に割り当てるようになっているため、
要素数がある程度増えてくると割り当て機能が線形性能ではいられなくなるのでは、と思う。

単連結リストと双方向連結リストの違いについては、
単連結リストの方が処理時間が短く、
前に述べたように要素の操作一回当たり単連結リストの方が少ないコストで済んでいるからであろうと思う。