単連結リストの整列 #74 スケーリング指数

gnuplot

直線的なプロット点が描かれれば直線を引きたくなるのは当然である。
gnuplotには回帰分析を行って与えられた関数に当てはめる機能があるので、
これを使って直線のパラメータを求めてみる。

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

両対数プロットでの回帰直線を求めるために、
回帰直線の式はaとbをパラメータとしてax+bとし、
コマンドfitに与えるデータはusing節を使って自然対数値に変換したものを使う。
解析で求められたパラメータは、

show variables a
show variables b

        Variables beginning with a:
        a1 = 2.00492666277766
        a2 = 2.00433041373949
        a3 = 2.94060857317216

        Variables beginning with b:
        b1 = -0.730207692537729
        b2 = -1.41618385241686
        b3 = -9.89583262659468

であった。
比較回数と交換回数の次数は2.0、所要時間の次数は2.9である。
比較・交換回数が要素数の二次オーダ、所要時間が三次オーダという理論的な推測が合っていたことが分かる。

この回帰直線を測定値のプロットに重ねてプロットするためには、
両対数プロットであることを考慮して、e^bx^aのプロットを行えばいい。

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

set key left top
set logscale xyy2
set pointsize 1.5
set xlabel "number of elements in a list"
set ytics nomirror 1000, 10 format "10^%L"
set ylabel "counts of comparisons, swaps"
set y2tics 100, 10 format "10^%L"
set y2label "elapsed time of 100 trials / ms"
set y2range [100:200000]
plot [100:2000] [1000:2000000] \
  'plot1.dat' using 1:2 title "#comps", \
  ''  using 1:3 lc rgb "forest-green" title "#swaps", \
  '' using 1:4 axis x1y2 title "elapsed time", \
  g(x,a1,b1) title sprintf("#comps scaling exponent %.4g", a1), \
  g(x,a2,b2) lc rgb "forest-green" title sprintf("#swaps scaling exponent %.4g", a2), \
  g(x,a3,b3) lc 3 axis x1y2 title sprintf("elapsed scaling exponent %.4g", a3)