単連結リストの整列 #95 隣接交換法、基本選択法、基数ソートの時間計算量のオーダ

gnuplot

前回の結果から要素数に対する処理時間のスケーリング指数を回帰分析で求めてみよう。

f(x,a,b) = a * x + b
fit f(x,a1,b1) 'result2.dat' using (log($1)):(log($2)) via a1, b1
fit f(x,a2,b2) 'result2.dat' using (log($1)):(log($3)) via a2, b2
fit f(x,a3,b3) 'result2.dat' using (log($1)):(log($4)) via a3, b3
fit f(x,a4,b4) 'result2.dat' using (log($1)):(log($5)) via a4, b4

show variables a
show variables b

データファイル'result2.dat'には、
1列目に要素数、
2と3列目に、双方向連結リストを隣接交換法と基本選択法で整列した場合、
4と5列目に、単連結リストと双方向連結リストを基数ソートした場合の処理時間が収められている。
各処理時間のスケーリング指数は、

        Variables beginning with a:
        a1 = 2.0398299967599
        a2 = 2.03472069999181
        a3 = 0.999919056120516
        a4 = 1.0197278956308

        Variables beginning with b:
        b1 = -7.11789606819258
        b2 = -7.53492750876627
        b3 = -2.40292487123797
        b4 = -2.45779765801523

隣接交換法と基本選択法の時間計算量が要素数に対する二次オーダになるのに対して、
基数ソートの場合は一次オーダになることが分かる。
前の結果では1から少し離れていた基数ソートの指数は、
データ数を増やすことで推測どおり1になった。
結果をプロットしてみよう。

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

set key right bottom
set logscale xy
set pointsize 1.5
set xtics (500,1000,2000,4000)
set xlabel "number of elements in a list"
set ytics format "10^%L"
set ylabel "elapsed time of 100 trials / ms"
plot [400:5000] [20:20000] \
  'result2.dat' using 1:2 title "double, bubble: elapsed", \
  'result2.dat' using 1:3 title "double, selection: elapsed", \
  'result2.dat' using 1:4 title "single, radix: elapsed", \
  'result2.dat' using 1:5 title "double, radix: elapsed", \
  g(x,a1,b1) lc 1 title sprintf("double, bubble: scaling exponent %.4g", a1), \
  g(x,a2,b2) lc 2 title sprintf("double, selection: scaling exponent %.4g", a2), \
  g(x,a3,b3) lc 3 title sprintf("single, radix: scaling exponent %.4g", a3), \
  g(x,a4,b4) lc 4 title sprintf("double, radix: scaling exponent %.4g", a4)


隣接交換法と基本交換法が二次オーダ、基数ソートが一次オーダとなっている。
また、基本選択法が隣接交換法よりもこのデータでは速い。
単連結リストの方が双方向連結リストよりも基数ソートによる処理時間が短いようにも見える。
双方向連結リストのデータ点のばらつきから見て、それは誤差の範囲なのかもしれないし、
要素1個当たり1個のリンク情報を操作するだけの単連結リストに比べて、
2個のリンク情報を操作する必要のある双方向連結リストが、
ほんの少しだけ処理に時間がかかることを表しているのかもしれない。
判断するには、まだ計測に使うリストの要素数や計測の試行回数が少ないのかもしれない。