[algorithm] C-R Sort の性能
http://d.hatena.ne.jp/tkuro/20080529/1212050357
のつづき。
rdtscを使って所用クロック数を調べてみる。手元のマシンはかなり非力＆省スペース。
model name : Intel(R) Pentium(R) 4 CPU 2.40GHz Family F model 2 step 7
cache size : 512 KB
MemTotal: 507856 kB
MemFree: 277200 kB
こりゃあんまり大きな値では実験できなさそう。
測定結果
| 要素数 | C-R Sort(clk) | QuickSort(clk) | 比率 |
|---|---|---|---|
| 10 | 4540 | 4228 | 0.931 |
| 100 | 28824 | 24904 | 0.864 |
| 1000 | 276596 | 277192 | 1.002 |
| 10000 | 3350904 | 3437820 | 1.026 |
| 100000 | 38073980 | 40520836 | 1.064 |
| 1000000 | 370943596 | 480289824 | 1.295 |
| 10000000 | 3863351092 | 5542817380 | 1.435 |
グラフにする意味無いか。
確かに O(n)になってるっぽ。10 ^8以上だとスラッシングで大変なことになってしまった。なんせ出力用のメモリが別に必要だから二倍以上だし仕方ない。集合が十分にでかっくてメモリがふんだんにある場合は有利、ってところか。それにしても富豪を通り越したブルジョアプログラミング気分。
