単連結リストの整列 #79 双方向連結リストの時間性能

単連結リストを用いた#71のコードによる整列の所要時間の計測を双方向連結リストで行ってみる。
コンパイル時に-DNOSORTオプションを与えて整列処理なしで実行すると、

# nelems ncmps nswps elapsed
200 0.0 0.0 0.0
300 0.0 0.0 0.0
400 0.0 0.0 0.0
600 0.0 0.0 0.0
800 0.0 0.0 0.0
1200 0.0 0.0 0.0
1600 0.0 0.0 0.0

なので、双方向連結リストでも初期化等に必要な時間は無視していいと思う。
整列処理を行わせると、

# nelems ncmps nswps elapsed
200 19759.3 9878.0 41.7
300 44613.6 22434.0 93.8
400 79462.8 40089.3 187.5
600 179024.9 89819.1 375.0
800 318956.3 159787.6 708.3
1200 718483.7 358853.3 1531.2
1600 1277827.0 642036.1 2750.0

となった。
リストの要素の値に使っている乱数を作り出す種は固定してあるので、
要素の比較と交換の回数は#71で出した単連結リストの結果と全く同じになっており、
整列処理に対する双方向連結リストの実装の正当さを示している。

整列処理の所要時間は要素数が大雑把に2の平方根倍されるごとに2倍の時間がかかっている。
これが単連結リストでは約3倍で、つまり要素数に対して三乗オーダで増加していた所要時間が、
双方向連結リストでは要素数に対して二乗オーダで増加していることになる。
また、双方向連結リストの方が要素数100程度以上では、
単連結リストより早く処理できそうだということが分かる。