単連結リストの整列 #80 要素数に対するスケーリング指数の比較

gnuplotの回帰分析機能を使って、
所要時間を要素数の冪関数へフィッティングして、そのパラメータを求めてみる。

f(x,a,b) = a * x + b
fit f(x,a4,b4) 'plot2.dat' using (log($1)):(log($3)) via a4, b4
fit f(x,a5,b5) 'plot2.dat' using (log($1)):(log($4)) via a5, b5
fit f(x,a3,b3) 'plot1.dat' using (log($1)):(log($4)) via a3, b3

show variables a
show variables b

        Variables beginning with a:
        a4 = 2.00433041373949
        a5 = 2.00612884132541
        a3 = 2.94060857317216

        Variables beginning with b:
        b4 = -1.41618385241686
        b5 = -6.87292540725565
        b3 = -9.89583262659468

データファイルplot2.datは双方向連結リストにおける出力である。
plot1.datは以前に出した単連結リストでの出力である。
要素の比較と交換の回数は単・双ともに同じであるので、
とりあえず回帰直線の傾きの比較のために交換回数だけ見てみることにした。

結果をプロットしてみる。

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

set key lmargin top font ",10"
set logscale xyy2
set pointsize 1.5
set xlabel "number of elements in a list"
set ytics nomirror 100, 10 format "10^%L"
set ylabel "counts of swaps"
set y2tics 10, 10 format "10^%L"
set y2label "elapsed time of 100 trials / ms"
set y2range [10:200000]
plot [100:2000] [100:2000000] \
  'plot2.dat' using 1:3 title "#swaps", \
  ''          using 1:4 axis x1y2 lc rgb "forest-green" title "d-linked elapsed time", \
  'plot1.dat' using 1:4 axis x1y2 title "s-linked elapsed time", \
  g(x,a4,b4) title sprintf("#swaps scaling exponent %.4g", a4), \
  g(x,a5,b5) axis x1y2 lc rgb "forest-green" title sprintf("d-linked elapsed scaling exponent %.4g", a5), \
  g(x,a3,b3) axis x1y2 lc 3 title sprintf("s-linked elapsed scaling exponent %.4g", a3)

単連結リストの所要時間が要素数の三乗で増加するのに対して、
双方向連結リストでは二乗の冪関数にフィットする。
そのため、この回帰直線は要素数に対する交換回数の回帰直線と平行になっている。
双方向連結リストでは要素の交換操作一回当たり定数時間で終えることができるため、
所要時間が交換回数と同じ次数になる。
また、100よりもっと少ない要素数のリストでも、
双方向連結リストの方が早く整列処理が終わるであろうことがプロットから読み取れる。