単連結リストの整列 #73 操作回数と所要時間のプロット

数値では分かりにくいので、横軸を要素数、縦軸を操作回数や所要時間で両対数プロットしてみる。
プロットには超定番gnuplotを使う。

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"

使用したデータファイルplot1.datには途中打ち切りありのlistsortを使用した時の
測定プログラムの実行結果の出力をそのまま入れてある。

操作回数、所要時間ともに要素数の増加とともに両対数プロットでは直線的に増加していることが見て取れる。
つまり、どの値も要素数の冪関数的になっているといえる。
操作回数が左軸、所要時間が右軸で、値としては両者は違うが、
対数スケールで両軸の最大値と最小値の差は同じになるようにプロットしている。
そのため、見た目でも比較回数や交換回数のプロットの傾きよりも所要時間のプロットの傾きの方が大きいことには意味がある。
つまり、冪関数の次数は所要時間のほうが大きいことを意味している。