実行画面
ソースコードをコンパイルしてプログラムを実行すると、以下のようなコンソール画面に計測結果が表示されます。
これをリダイレクトにてファイルに落とし、そのファイルをExcelに入れてグラフなどに加工して視覚化します。
計測結果
結果を見ると型による違いは特に現れませんでした。それぞれの結果をグラフにすると傾向がよく分かります。int
型の計測結果よりもstd::string
の結果の方が、違いが顕著に出ているため分かりやすいです。
std::string
のグラフを見て分かることは、高速なコードはstd::sort()
であり、これは型を変えても、項目数を増やしても同じ傾向でした。
逆に、低速なコードはstd::multiset<>
であり、これはstd::list<>
のsort()
と同等かそれよりも遅いという結果でした。
特に気になったのは、std::multiset<>
やstd::list<>
では、項目数が10万件以下の場合、ソート処理時間にかなりのばらつきがあったことです。まさに桁違いに遅い結果が計測されました。この現象については、ソート処理よりも、何らかの原因でデータ構造を再構築することになり、メモリのアロケート処理などで大きく時間をロスしているのではないかと推測します。それにしても、この処理時間がここまでばらつくとは予想外の結果でした。
この結果を素直に受け止めるのなら、std::multiset<>
やstd::list<>
は、データのソートを目的として使うべきではないことになります。筆者は過去にソートを目的としたコードにstd::multiset<>
を使ったことがありますが、これについてはなるべく早く訂正すべきであると素直に反省しています。
個人的な話になりますが、今回の大きな収穫は「qsort()
よりも、std::sort()
の方が早い」という計測結果です。よく「qsort()
よりもstd::sort()
の方が早いから、無条件にstd::sort()
を使え」とか、「std::sort()
は比較ルーチンを含みで最適化がかかるからqsort()
よりも高速なのだ」という話を聞いていました。これらの話をどこまで信じてよいものか疑問があったのですが、今回の計測結果で、その疑問が晴れました。
可読性の話
以下に、ソート処理の部分のみを抜き出してみました。
// 速度計測対象のソート処理
std::vector< _TYPE > vctr( data.begin(), data.end() ) ;
std::sort( vctr.begin(), vctr.end() ) ;
std::sort()
は、一番一般的というか、これが分かりにくいということはないと思われます。
// 速度計測対象のソート処理
std::multiset< _TYPE > set( data.begin(), data.end() ) ;
std::multiset<>
は、ソートをしているとは認識されないケースが多いと思われます。よって可読性としてはあまりよくないと判断します。
// 速度計測対象のソート処理
std::list< _TYPE > list( data.begin(), data.end() ) ;
list.sort() ;
std::list<>
は、比較的すっきりと分かりやすい記述になっていると思います。
std::vector< _TYPE > vctr( data.begin(), data.end() ) ; qsort( & vctr[0], // void *base, vctr.size(), // size_t num, sizeof( vctr[0] ), // size_t width, compare_string ) ;
qsort()
はC言語ですし、ポインタを使ったり、比較関数を用意したりと、書くのが面倒です。
ソート処理であることは分かるのですが、可読性というか、それ以前にバグが入り込みやすいコードです。C++のSTLが使える環境であれば、わざわざ使う意味はないでしょう。
以下に、個人的な感覚で可読性を評価した結果を示します。
記述量 | 分かりやすさ | バグ耐性 | 可読性(総合) | |
std::sort() | ○ | ○ | ○ | ○ |
std::multiset<> | ○ | × | ○ | △ |
std::list<> | ○ | ○ | ○ | ○ |
qsort() | × | △ | × | × |
結論
以下に、個人的な感覚で評価した結果を示します。
速度 | 可読性 | 総合評価(ランキング) | |
std::sort() | ◎ | ○ | ◎ |
std::multiset<> | × | △ | × |
std::list<> | × | ○ | × |
qsort() | ○ | × | × |
「C++のSTLにはデータをソートする方法がいくつか存在するが、ソート処理を簡単に、かつ効率のよいコードはどれか…」という疑問の答えは、特別な理由がない限り「ソート処理はstd::sort()
を使うべき」という結論になりました。