SHOEISHA iD

※旧SEメンバーシップ会員の方は、同じ登録情報(メールアドレス&パスワード)でログインいただけます

CodeZine編集部では、現場で活躍するデベロッパーをスターにするためのカンファレンス「Developers Summit」や、エンジニアの生きざまをブーストするためのイベント「Developers Boost」など、さまざまなカンファレンスを企画・運営しています。

特集記事

C++におけるデータのソート方法の比較

STLでの最適なソート方法の検討


  • X ポスト
  • このエントリーをはてなブックマークに追加

実行画面

 ソースコードをコンパイルしてプログラムを実行すると、以下のようなコンソール画面に計測結果が表示されます。

実行画面
実行画面

 これをリダイレクトにてファイルに落とし、そのファイルをExcelに入れてグラフなどに加工して視覚化します。

計測結果

 結果を見ると型による違いは特に現れませんでした。それぞれの結果をグラフにすると傾向がよく分かります。int型の計測結果よりもstd::stringの結果の方が、違いが顕著に出ているため分かりやすいです。

結果の比較(std::string)
結果の比較(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::sort()
// 速度計測対象のソート処理
std::vector< _TYPE >  vctr( data.begin(), data.end() ) ;
std::sort( vctr.begin(), vctr.end() ) ;

 std::sort()は、一番一般的というか、これが分かりにくいということはないと思われます。

std::multiset<>
// 速度計測対象のソート処理
std::multiset< _TYPE >  set( data.begin(), data.end() ) ;

 std::multiset<>は、ソートをしているとは認識されないケースが多いと思われます。よって可読性としてはあまりよくないと判断します。

std::list<>
// 速度計測対象のソート処理
std::list< _TYPE >  list( data.begin(), data.end() ) ;
list.sort() ;

 std::list<>は、比較的すっきりと分かりやすい記述になっていると思います。

qsort()
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()を使うべき」という結論になりました。

この記事は参考になりましたか?

  • X ポスト
  • このエントリーをはてなブックマークに追加
特集記事連載記事一覧

もっと読む

この記事の著者

山崎 敏(ヤマザキ サトシ)

フリーでプログラミングの仕事をしたり、本や雑誌の原稿を書いたり、株の売買をしたりして、つつましく暮らしております。よろしくお願いします。やまざき@BinaryTechnology

※プロフィールは、執筆時点、または直近の記事の寄稿時点での内容です

この記事は参考になりましたか?

この記事をシェア

  • X ポスト
  • このエントリーをはてなブックマークに追加
CodeZine(コードジン)
https://codezine.jp/article/detail/394 2006/05/30 11:58

おすすめ

アクセスランキング

アクセスランキング

イベント

CodeZine編集部では、現場で活躍するデベロッパーをスターにするためのカンファレンス「Developers Summit」や、エンジニアの生きざまをブーストするためのイベント「Developers Boost」など、さまざまなカンファレンスを企画・運営しています。

新規会員登録無料のご案内

  • ・全ての過去記事が閲覧できます
  • ・会員限定メルマガを受信できます

メールバックナンバー

アクセスランキング

アクセスランキング