単連結リストの整列 #97 要素数の範囲と密度を増やす

C gnuplot

前回の計測結果は大まかな傾向しか見えず、プロット点が少ないと思うので増やしてみた。

...snip
int main(void)
{
    const int nelems[] = {1000, 1778, 3162, 5623, 10000, 17782, 31623, 56234, 100000, 177828, 316228, 562341, 1000000};
    const int ntrials[] = {6325, 3557, 2000, 1124, 632, 356, 200, 112, 63, 36, 20, 20, 20};
...snip

試行回数は最低でも20回くらいはほしかったので、
要素数が多くなっても20でサチらせてこれを下回らないようにしている。
実行結果は以下の通り。

result4.dat
1000 91.1 105.1
1778 165.3 189.8
3162 295.5 339.5
5623 522.2 598.8
10000 943.0 1077.5
17782 1682.6 1941.0
31623 3160.0 3620.0
56234 6526.8 7258.9
100000 18984.1 20174.6
177828 49027.8 51027.8
316228 117750.0 123100.0
562341 254600.0 264350.0
1000000 500800.0 521700.0

前回と同じく各列は要素数、単連結リストの所要時間、双方向連結リストの所要時間である。
プロットすると、

set key right bottom
set logscale xy
set pointsize 1.5
set grid
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 [500:2000000] [50:1000000] \
  'result4.dat' using 1:2 title "single: elapsed", \
  'result4.dat' using 1:3 lc 3 title "double: elapsed"


要素数31623あたりを境界にして傾向が変化している。
これ以下の要素数の領域では単純に線形に増加しているのに対して、
これ以上では、100000あたりで最も急激に増加した後、
次第にその増加傾向が緩やかになっていくという少し複雑な様相を示す。
どういう機序がその背景にあるのかちょっとよく分からない。

要素数の少ない領域でのスケーリング指数を確認するために、
fitに与えるデータ点を31623以下の最初の7点に限定してみる。

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

show variables a
show variables b

everyでのデータ点のインデックスは0オリジンなので、
every ::::6で第0点から第6点までの7点がfitに与えられる。

        Variables beginning with a:
        a1 = 1.01996120497583
        a2 = 1.01888657149965

        Variables beginning with b:
        b1 = -2.535297066158
        b2 = -2.38759754847475

この領域では要素数に関して一次オーダの時間計算量になっている。
これも込みでプロットし直すと、

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

set key right bottom
set logscale xy
set pointsize 1.5
set grid
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 [500:2000000] [50:1000000] \
  'result4.dat' using 1:2 title "single: elapsed", \
  'result4.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)