単連結リストの整列 #93 バケツソートによる基数ソートの時間計算量

gnuplot

書き忘れたが、前回の結果はUbuntu上で動作させたものである。
この結果から、かなり面倒くさいリスト操作を色々やっているにも関わらず、
バケツソートによる基数ソートは非常に速いことが分かる。
また、この基数ソートの実装では、
ある要素からその一つ前の要素を求めるような操作が無いため、
単連結リストと双方向連結リストに処理時間の差はあまりないようだ。

時間計算量のオーダも確認しておこう。
例によってgnuplotの回帰分析機能fitを使う。

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

show variables a
show variables b

結果データ'result.dat'には、一列目に要素数、
二列目から五列目に「単、隣接交換」「双、隣接交換」「単、基数」「双、基数」の経過時間が入っている。
求まった経過時間の要素数に対するスケーリングパラメータは、

        Variables beginning with a:
        a1 = 2.94642725643908
        a2 = 2.04851813198259
        a3 = 1.14513295748552
        a4 = 1.08907966151703

        Variables beginning with b:
        b1 = -9.89770937741881
        b2 = -7.17777809948051
        b3 = -3.30887236218476
        b4 = -2.91151141878326

データ点と回帰直線をプロットする。

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

set key left top
set logscale xy
set pointsize 1.5
set xlabel "number of elements in a list"
set ytics format "10^%L"
set ylabel "elapsed time of 100 trials / ms"
plot [100:2000] [10:200000] \
  'result.dat' using 1:2 title "single, bubble: elapsed", \
  'result.dat' using 1:3 title "double, bubble: elapsed", \
  'result.dat' using 1:4 title "single, radix: elapsed", \
  'result.dat' using 1:5 title "double, radix: elapsed", \
  g(x,a1,b1) lc 1 title sprintf("single, bubble: scaling exponent %.4g", a1), \
  g(x,a2,b2) lc 2 title sprintf("double, bubble: 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前後と、1よりも少々大きめなのは、
要素数が少ない領域でプロット点がばらついていることから、
処理時間を計測するには短過ぎて誤差を含んでいるからではないかと思う。
要素数が多いほどばらつきが無くなっているようなので、
さらに要素数を増やして計測すればパラメータは1に近づくのではないか？
また、試行回数を増やしてもいいだろうと考える。

いずれにせよ、基数ソートが圧倒的に速い。
また、要素数に対する時間計算量もほぼ一次オーダであり、
オンメモリの範囲内で済むのなら要素数の増加にも強いだろう。