2010-10-30

（後日記）注意：以下ではCompTupleByを紹介していますが、C++11の使える環境ではラムダ式というもっと便利なものがあるので、こうした工夫は前時代の遺物になります。（作った時は便利だったんだけどね）なので以下歴史家の人以外は読まないで下さい。

// // CompTupleBy.h (C) 2010 nurs // #pragma once #pragma warning( disable : 4244 ) #include <iostream> #include <tuple> template< int id > struct CompTupleBy { template<class T> bool operator()( const T& a, const T& b ) const { return std::get<id>(a) < std::get<id>(b); } };

// 例えばこんなタプル型を考えます typedef tuple< int, string, float > Tuptype; // tupleのコンテナを用意 vector< Tuptype > tupv; // 0番目の要素でソート sort( tupv.begin(), tupv.end(), CompTupleBy<0>() ); // 1番目の要素でソート sort( tupv.begin(), tupv.end(), CompTupleBy<1>() );

#include <iostream> #include <vector> #include <string> #include <algorithm> using namespace std; #include "poc_foreach.h" #include "sort_tuple_by.h" // 例えばこんなタプル型を考えます typedef tuple< int, string, float > Tuptype; // 結果確認用 void lc_show_result( const vector< Tuptype >& tupv ) { NURS_FOREACH( tupv, const Tuptype& itup ){ cout << get<0>(itup) <<"\t" << get<1>(itup) <<"\t" << get<2>(itup) << endl; }// itup return; } // メイン関数 int main( void ) { // tupleのコンテナを用意 vector< Tuptype > tupv; { tupv.push_back( make_tuple( 0, "Taro", 1.34 ) ); tupv.push_back( make_tuple( 77, "Aaron", 1.33 ) ); tupv.push_back( make_tuple( 19, "Buchn", 0.33 ) ); tupv.push_back( make_tuple( 3, "Vermi", 1.23 ) ); } // 0番目の要素でソート cout<<" ▼"<<endl; sort( tupv.begin(), tupv.end(), CompTupleBy<0>() );// ★ここな ::lc_show_result( tupv ); cout<<endl; // 1番目の要素でソート cout<<"\t ▼"<<endl; sort( tupv.begin(), tupv.end(), CompTupleBy<1>() );// ★ここな ::lc_show_result( tupv ); cout<<endl; // 2番目の要素でソート cout<<"\t\t ▼"<<endl; sort( tupv.begin(), tupv.end(), CompTupleBy<2>() );// ★ここな ::lc_show_result( tupv ); cout<<endl; getchar(); return 0; }

（後日記）注意：以下CompTupleByはC+11のラムダ式でとって変わられるべき前時代の遺物ですので気にせず、stable_sortに関する説明のみ参考とするようにして下さい。

さて、CompTupleBy を得た今、std::sortと、std::stable_sortとの違いを実験してみたくなったので行ってみようか。よく、エクセルとかで、あるカラムでソートした後、別のカラムでまたソートなんかした時に、2回目のソートでは1回目のソートの結果は保たれるのだろうかなんてことが気になったことはないかい。名前でソートした後、グループでソートしたら、同じグループの人たちについてはすでに名前順にちゃんと並んでいることを期待してしまうよな。
std::stable_sortは、std::sortとは違って、ソート時の要素比較上同等と認められる要素についてはそれらの間の既存の順番を保存してくれるエレガントなソート処理を保障してくれるアルゴリズムだよ。これを、「static」もしくは「stable」なソートと呼んだりするらしい。
では実験だ。まず、二つの整数をペアにして覚えておけるtuple型を用意する。次に、0から5までの値のペアを銘々に組み合わせて持たせたtupleインスタンスを６ｘ６、計36個作成しvectorに詰める。そしてこれの順番をランダムにシャッフルさせ、CompTupleByファンクタを使って、まずは一つ目の整数の値でソートし、次に二つ目の値でソートするということを、std::sort、およびstd::stable_sortそれぞれについてやってみよう。実験用のプログラムは以下のようになるよ。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#include "poc_foreach.h"
#include "comp_tuple_by.h"

// こんなタプル型を考えます
typedef tuple< int, int > Tuptype;

// 結果確認用
void lc_show_result( const vector< Tuptype >& tupv )
{
  NURS_FOREACH( tupv, const Tuptype& itup ){
     cout << get<0>(itup)<< ",";
  }// itup
  cout<< endl;
  NURS_FOREACH( tupv, const Tuptype& itup ){
     cout << get<1>(itup)<< ",";
  }// itup
  cout<< endl;
  return;
}

// メイン関数
int main( void )
{
  // tupleのコンテナを用意
  vector< Tuptype > tupv;
  {
    const int m = 6;
    const int n = 6;
    // タプルのインスタンスを作成
    for( int i=0; i<m; ++i ){
      for( int j=0; j<n; ++j ){
        tupv.push_back( make_tuple( i, j ) );
      }// j
    }// i
    // シャッフル！
    for( int i=0; i<200; ++i ){
      swap(
        tupv[ rand()/(float)RAND_MAX * (m*n-1) ],
        tupv[ rand()/(float)RAND_MAX * (m*n-1) ]
        );
    }// i
  }

  
  cout<< "std::sort"<<endl;

  // 上段の値でstd::sort
  cout<<"①：まず上段で std::sort"<<endl;
  sort( tupv.begin(), tupv.end(), CompTupleBy<0>() );
  ::lc_show_result( tupv );
  cout<<endl;

  vector< Tuptype > tupv_1 = tupv;

  // 下段の値で std::sort
  cout<<"②：①の結果に対し下段でstd::sort"<<endl;
  sort( tupv.begin(), tupv.end(), CompTupleBy<1>() );//●
  ::lc_show_result( tupv );
  cout<<endl;

  tupv = tupv_1;
  // 下段の値で std::stable_sort
  cout<<"③：①の結果に対し下段でstd::stable_sort"<<endl;
  stable_sort( tupv.begin(), tupv.end(), CompTupleBy<1>() );//●
  ::lc_show_result( tupv );
  cout<<endl;

  getchar();
  return 0;
}

そして出力結果は以下のようになった。

いかがだろうか。問題は2回目のソートで、sortを使うかstable_sortを使うかの違いだ。sortを使った場合は、1回目のソートでせっかく順に並んでいた上段の順番が容赦なく崩されてしまい、下段の数値について綺麗に並んでいるだけなのに対し、stable_sortを使った場合は、下段の値が同じ要素についてみてみるとその上段の値はどれも0,1,2,3,4,5と綺麗に並んでおり、まさに既存の上段の並びを極力維持しつつ、下段をソートするということがちゃんと達成されていることがわかるね。
最後にアルゴリズムの効率だけど、STLドキュメントの、Complexityという節を見てみると、stable_sortの方が高機能な分だけ、処理コストもかかるようだ。まず通常のsortが、O(NlogN)であると。stable_sortでは、メモリが十分にある場合には、sortと同じく、O(NlogN)だが、メモリが十分に利用できないには最悪O(N(logN)^2)になるということだ。なのでメモリが十分にある環境では、パフォーマンスの違いについては心配しなくてよさそうな感じだね。

nursの日記

CompTupleBy〜tupleのソート

そしてstable_sortを知る