それも、できるだけ高速にソートしたい、という機会はありませんか？
私はありました。そこで、ソートアルゴリズムの速さを計ってみました。
●測定環境
OS：Windows Vista Home Premium SP2 32ビット
CPU：Intel Core(TM)2 Duo T8100 @2.10GHz 2.10GHz
メモリ：2.00GB
コンパイラ：gcc 4.7.0
コンパイルオプション：-O2
●測定方法
xorshiftを用いてランダムに生成したデータ（unsigned int）を、１セットの実験では同じデータを使用し、
昇順に並べ替える関数を呼び、その実行時間をtimeGetTime()関数を用いて計測した。
データを変え、3回づつ測定し、平均を取った。
●測定対象のコード
１．qsort
► スポイラーを表示
► スポイラーを表示
► スポイラーを表示
時間の単位はミリ秒である。
N radix qsort std heap shell set bubble
100 0 0 0 0 0 0 0
316 0 0 0 0 0 0 0
1000 0 0 0 0 0 0 3
3162 0 1 0 1 0 1 21
10000 0 2 1 2 2 4 222
31623 1 7 2 9 7 15 2314
100000 2 26 10 31 25 86 24639
316228 13 112 46 150 120 491
1000000 34 323 119 476 453 1565
3162278 171 1199 450 2451 2136 7404
10000000 354 3502 1378 7928 6832 23900
31622777 1204 11955 4723 30236 28120
100000000 17625 39821 15842 120407 116166- 時間のグラフ1
- sort_graph.png (8.62 KiB) 閲覧数: 564 回
- 時間のグラフ2
- sort_graph2.png (7.97 KiB) 閲覧数: 536 回
・予想通り、ほぼO(N)とされている基数ソートがほとんどの場合最速である。
N=100000000でstd::sortに抜かれているのは、作業用メモリ確保のオーバーヘッドか？
・qsortはstd::sortより遅い。比較関数をいちいち呼び出す必要があるからであると推測できる。
・今回は、ヒープソートよりシェルソートの方が速かった。
ヒープソートの実装を改善すれば、もう少し高速になるかな？
・std::multisetに要素を挿入すると勝手に昇順になるが、その処理は非常に遅い。
また、誤ってstd::setを使用すると重複した要素が削除されてしまうので注意が必要。
・バブルソートはオワコン。取り柄は実装が簡単なことと安定であることのみ。
●結論
・Nが10～100程度ならバブルソートでも可。
バブルソートは、低速だが実装が簡単であるため、
ソートにおけるワーシャル-フロイド法のようなものであると言える。
・std::multisetをソートだけのために使用してはいけない。でもアロケータを変えれば少し高速になるかも。
・あえてヒープソートやシェルソートを実用的に使用する意味はないと考えられる。
・qsortは遅い。C++ならstd::sortを使用するべき。
・基数ソートは高速であるが、メモリを多く消費し、さらに適用範囲が限定されるため、
かなり必死に定数倍高速化しないといけない状況でなければstd::sortで十分。
オフトピック
ご意見、ご感想お待ちしております。
メニュー
カレンダー
Clock
最新メンバー
投稿数
統計データ
Link to us
カウンター