コードの解説
ソースコードはmain()関数1つとソート計測用関数4つ、合計5つの大きな関数を1つのファイル「sort_test.cxx」にまとめて記述しています。以下、それぞれの関数について順番に解説をします。
| 関数名 | 内容 |
std_sort() | std::sort()の実装 |
std_multiset() | std::multiset<>の実装 |
std_list() | std::list<>の実装 |
c_qsort() | qsort()の実装 |
main() | メイン関数 |
std::sort()の実装
最初は、std::sort()アルゴリズムを使ったソート処理の計測コードを書きます。
コードの流れとしては、まず、std::vector<> を使ってソート対象となるデータを確保します。その後、
std::random_shuffle( data.begin(), data.end() ) ;
を使って、データを適当にかき混ぜます。そして、std::sort()の処理速度を計測します。
この時、誤差を分散させ結果を平均化するために同じ処理を30(LOOP_COUNT)回計測します。また、データの項目数を増減させて、処理速度の変化を計測します。項目数はSIZE_TBL[]にて固定値で用意しています。
static const int SIZE_TBL[] = { 10000, 50000, 100000, 200000, 400000 } ;
データ項目数（SIZE_TBL）と計測回数（LOOP_COUNT）は、それぞれ4つのソート計測関数の中でループに使っています。
また、4つのソート計測関数の中から、共通に使っている小さな関数として、type_name()とdata_set()とput()の3つがあります。
type_name()は、データの型名を表示するために使っています。data_set()は、intの数値から、それぞれ、int、double、std::stringのデータを返すというものです。put()は、printf()をして結果を表示するための関数です。
ソート計測用の関数はtemplateを使って、型に依存しない書き方で書いているのですが、それぞれ、型に依存してしまう部分を別の関数として抜き出した形になっています。
サンプルプログラム「sort_test.cxx」std_sort()
#include <stdio.h> // printf() // timeGetTime() #include <windows.h> // mmsystem.h の中で UINT とかを使っている… #include <mmsystem.h> // timeGetTime() #pragma comment( lib, "winmm.lib" ) // timeGetTime() リンク指定 #pragma warning( disable : 4786 ) // VCの無意味で不快なwarningを消す #include <string> // std::string #include <vector> // std::vector<> #include <algorithm> // std::sort(), std::random_shuffle() char * type_name( int in ) { return "int" ; } char * type_name( double in ) { return "double" ; } char * type_name( std::string in ) { return "std::string" ; } // ソート対象となるデータを作る void data_set( int & out, int in ) { out = in ; } void data_set( double & out, int in ) { out = (double)in ; } void data_set( std::string & out, int in ) { static char buff[10] ; sprintf_s( buff, "%08x", in ) ; out = buff ; } // sort結果を簡易表示 inline void put( const int in_front, const int in_back ) { printf( "%d ... %d\n", in_front, in_back ) ; } inline void put( const double in_front, const double in_back ) { printf( "%f ... %f\n", in_front, in_back ) ; } inline void put( const std::string in_front, const std::string in_back ) { puts( (in_front + " ... " + in_back).c_str() ) ; } static const int LOOP_COUNT = 30 ; static const int SIZE_TBL[] = { 10000, 50000, 100000, 200000, 400000 } ; template< typename _TYPE > void std_sort() { for ( int s=0, z=sizeof(SIZE_TBL)/sizeof(SIZE_TBL[0]) ; s<z ; ++s ) { // ソート対象となるデータを確保 std::vector< _TYPE > data ; data.resize( SIZE_TBL[s] ) ; for ( int i=0 ; i<SIZE_TBL[s] ; ++i ) data_set( data[i], i+1 ) ; printf( "\n" ) ; printf( "std::sort( std::vector< %s > )\n", type_name( data[0] ) ) ; printf( "no.\tsize\tsort(ms)\tresult\n" ) ; for ( int t=0 ; t<LOOP_COUNT ; ++t ) { // かき混ぜる std::random_shuffle( data.begin(), data.end() ) ; printf( "%d\t%d\t", t+1, data.size() ) ; unsigned long start_time = timeGetTime() ; // 計測開始時間 // 速度計測対象のソート処理 std::vector< _TYPE > vctr( data.begin(), data.end() ) ; std::sort( vctr.begin(), vctr.end() ) ; unsigned long end_time = timeGetTime() ; // 計測終了時間 printf( "%d\t", end_time - start_time ) ; // sort結果を簡易表示 put( *vctr.begin(), *(vctr.end()-1) ) ; } // end for LOOP_COUNT } //end for s }
std::multiset<>の実装
std_multiset()関数は、前のstd_sort()関数とまったく同じ構成です。ソート処理の部分がstd::multiset<>になっている以外はすべて同じと言えます。
サンプルプログラム「sort_test.cxx」std_multiset()
#include <set> // std::multiset<> template< typename _TYPE > void std_multiset() { for ( int s=0, z=sizeof(SIZE_TBL)/sizeof(SIZE_TBL[0]) ; s<z ; ++s ) { // ソート対象となるデータを確保 std::vector< _TYPE > data ; data.resize( SIZE_TBL[s] ) ; for ( int i=0 ; i<SIZE_TBL[s] ; ++i ) data_set( data[i], i+1 ) ; printf( "\n" ) ; printf( "std::multiset< %s >\n", type_name( data[0] ) ) ; printf( "no.\tsize\tsort(ms)\tresult\n" ) ; for ( int t=0 ; t<LOOP_COUNT ; ++t ) { // かき混ぜる std::random_shuffle( data.begin(), data.end() ) ; printf( "%d\t%d\t", t+1, data.size() ) ; unsigned long start_time = timeGetTime() ; // 計測開始時間 // 速度計測対象のソート処理 std::multiset< _TYPE > set( data.begin(), data.end() ) ; unsigned long end_time = timeGetTime() ; // 計測終了時間 printf( "%d\t", end_time - start_time ) ; // sort結果を簡易表示 std::multiset< _TYPE >::iterator it = set.end() ; put( *set.begin(), *(--it) ) ; } // end for LOOP_COUNT } // end for s }
std::list<>の実装
std_list()関数も、前のstd_sort(),std_multiset()関数とまったく同じ構成です。ソート処理の部分がstd::listに登録したあとsort()メソッドを呼んでいる形になっています。
サンプルプログラム「sort_test.cxx」std_list()
#include <list> // std::list<> template< typename _TYPE > void std_list() { for ( int s=0, z=sizeof(SIZE_TBL)/sizeof(SIZE_TBL[0]) ; s<z ; ++s ) { // ソート対象となるデータを確保 std::vector< _TYPE > data ; data.resize( SIZE_TBL[s] ) ; for ( int i=0 ; i<SIZE_TBL[s] ; ++i ) data_set( data[i], i+1 ) ; printf( "\n" ) ; printf( "std::list< %s >::sort()\n", type_name( data[0] ) ) ; printf( "no.\tsize\tsort(ms)\tresult\n" ) ; for ( int t=0 ; t<LOOP_COUNT ; ++t ) { // かき混ぜる std::random_shuffle( data.begin(), data.end() ) ; printf( "%d\t%d\t", t+1, data.size() ) ; unsigned long start_time = timeGetTime() ; // 計測開始時間 // 速度計測対象のソート処理 std::list< _TYPE > list( data.begin(), data.end() ) ; list.sort() ; unsigned long end_time = timeGetTime() ; // 計測終了時間 printf( "%d\t", end_time - start_time ) ; // sort結果を簡易表示 put( list.front(), list.back() ) ; } // end for LOOP_COUNT } //end for s }
qsort()の実装
c_qsort()関数は大筋では前の3つの関数と同じ構成です。ソート処理の部分がqsort()になっているのですが、型ごとに処理を分離しているので、templeteで書いている旨みが半減しています。
サンプルプログラム「sort_test.cxx」std_list()
int compare_int( const void * elem1, const void * elem2 ) { return *(int *)elem1 - *(int *)elem2 ; } int compare_double( const void * elem1, const void * elem2 ) { return int( *(double *)elem1 - *(double *)elem2 ) ; } int compare_string( const void * elem1, const void * elem2 ) { std::string & e1 = *(std::string *)elem1 ; std::string & e2 = *(std::string *)elem2 ; return e1 == e2 ? 0 : ( e1 > e2 ? 1 : -1 ) ; } template< typename _TYPE > void c_qsort() { for ( int s=0 ; s<(sizeof(SIZE_TBL)/sizeof(SIZE_TBL[0])) ; ++s ) { // ソート対象となるデータを確保 std::vector< _TYPE > data ; data.resize( SIZE_TBL[s] ) ; for ( int i=0 ; i<SIZE_TBL[s] ; ++i ) data_set( data[i], i+1 ) ; printf( "\n" ) ; printf( "qsort( std::vector< %s > )\n", type_name( data[0] ) ) ; printf( "no.\tsize\tsort(ms)\tresult\n" ) ; for ( int t=0 ; t<LOOP_COUNT ; ++t ) { std::random_shuffle( data.begin(), data.end() ) ; printf( "%d\t%d\t", t+1, data.size() ) ; unsigned long start_time = timeGetTime() ; // 計測開始時間 // 速度計測対象のソート処理 std::vector< _TYPE > vctr( data.begin(), data.end() ) ; if ( type_name( data[0] )[0] == 'i' ) // int { qsort( & vctr[0], // void *base, vctr.size(), // size_t num, sizeof( vctr[0] ), // size_t width, compare_int // int (__cdecl *compare) // (const void *elem1, const void *elem2) ) ; } if ( type_name( data[0] )[0] == 'd' ) // double { qsort( & vctr[0], // void *base, vctr.size(), // size_t num, sizeof( vctr[0] ), // size_t width, compare_double // int (__cdecl *compare) // (const void *elem1, const void *elem2) ) ; } if ( type_name( data[0] )[0] == 's' ) // std::string { qsort( & vctr[0], // void *base, vctr.size(), // size_t num, sizeof( vctr[0] ), // size_t width, compare_string // int (__cdecl *compare) //(const void *elem1, const void *elem2) ) ; } unsigned long end_time = timeGetTime() ; // 計測終了時間 printf( "%d\t", end_time - start_time ) ; // sort結果を簡易表示 put( *vctr.begin(), *(vctr.end()-1) ) ; } // end for LOOP_COUNT } //end for s }
メイン関数
最後に、main()関数です。タイマーの精度変更して、上記4つの関数をデータ型ごとに呼び出します。ソート対象のデータ型にはint、double、std::stringの3種類について計測します。
サンプルプログラム「sort_test.cxx」std_list()
int main() { timeBeginPeriod( 1 ) ; // タイマーの精度を 1ms にする std_sort <int>() ; std_multiset<int>() ; std_list <int>() ; c_qsort <int>() ; std_sort <double>() ; std_multiset<double>() ; std_list <double>() ; c_qsort <double>() ; std_sort <std::string>() ; std_multiset<std::string>() ; std_list <std::string>() ; c_qsort <std::string>() ; timeEndPeriod( 1 ) ; // タイマーの精度を元に戻す return 0 ; }
