とくにあぶなくないRiSKのブログ

危ないRiSKのブログだったかもしれない。本当はRiSKだけどググラビリティとか取得できるIDの都合でsscriskも使ったり。

降順のソート方法

降順のソート - Faith and Brave - C++で遊ぼう
によると

// 1
std::sort(v.begin(), v.end(), std::greater<Type>());

より

// 2
std::sort(v.rbegin(), v.rend());

の方がいいんじゃないか,とのこと。ちょっと調べてみましょうか。

2. の利点

  • コードが短い
  • Typeを考える必要がない

では 1. はどうなの?

速度

こっちにも利点があるのではないか? 1. の方が実行速度が速いのではないか?と思ったので実験。

#include<vector>
#include<limits>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<boost/progress.hpp>
#include<cassert>

int main()
{
 using namespace std; using namespace boost;

 typedef vector<int> vec;
 typedef vec::size_type vec_size;
 vec_size const size = 5000000;
 vec test1(size);
 for(vec_size n = 0; n != size; ++n)test1.push_back(rand());
 vec test2 = test1;

 {
  progress_timer t;
  sort(test1.begin(), test1.end(), greater<vec::value_type>());
 }
 {
  progress_timer t;
  sort(test2.rbegin(), test2.rend());
 }
 assert(test1 == test2);
}

実行結果:

$ g++4.6 a.cpp -O0 && ./a
12.58 s

26.97 s

$ g++4.6 a.cpp -O1 && ./a
1.91 s

2.75 s

$ g++4.6 a.cpp -O2 && ./a
1.84 s

2.02 s

やはり 1.の方が速いぞ!

まとめ

コーディングが楽なのは 2.。でも,実行速度を求めるなら 1. の方が速いよ。

追記:別解

コメントいただきました。

pepshiso 2011/02/12 16:17
Boost.Lambda + Boost.Range派です。

using namespace boost::lambda;
using namespace boost::range;
sort(v, _1 > _2);

これはいいですね。

追記2:VC++10の場合

Releaseモードでテストしてみると,1. と 2. の差はほとんどないようです。ほんのちょっとだけ 1. の方が速いかな,程度。十分な最適化があると 1. の速度の利点がほとんど無くなってしまいますね。
それでも,速度にこだわるなら 1. で!w