/** * @file sort_test5.cpp * @brief 安定ソートのテスト. * @note * ついでに他のソートも試してる... */ #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <string.h> #include <algorithm> #include <functional> #include <typeinfo> #include <string> #include <set> #include <vector> #include <list> #include "sort_etc.h" #include "quick_sort.h" #include "quick_sort_y.h" #include "merge_sort.h" #include "radix_sort.h" //#define CHECK_STABLE // 安定ソートの順番チェックをするなら定義 #ifdef CHECK_STABLE // 安定ソートチェックでは値を0〜255に限定しているのでビンソートも試してみる. #include "backet_sort.h" #endif // =========================================================================== using namespace std; #define MAC_STR_2(x) #x #define MAC_STR(x) MAC_STR_2(x) // 時間計測関係 #ifdef _WIN32 #include <windows.h> typedef unsigned __int64 PerfCnt_tick_t; PerfCnt_tick_t PerfCnt_getTick() { PerfCnt_tick_t c; QueryPerformanceCounter((LARGE_INTEGER*)&c); return c; } PerfCnt_tick_t PerfCnt_tickPerSec() { static PerfCnt_tick_t s = 0; if (!s) QueryPerformanceFrequency((LARGE_INTEGER*)&s); return s; } #elif defined LINUX #include <sys/resource.h> typedef double PerfCnt_tick_t; PerfCnt_tick_t PerfCnt_getTick() { struct rusage t; getrusage(RUSAGE_SELF, &t); return t.ru_utime.tv_sec * 1000000.0 + t.ru_utime.tv_usec; } #define PerfCnt_tickPerSec() 1000000.0 #else #include <time.h> typedef clock_t PerfCnt_tick_t; #define PerfCnt_getTick() clock() #define PerfCnt_tickPerSec() CLOCKS_PER_SEC #endif // 乱数生成. class Rand_XorShift { public: Rand_XorShift() { init(); } void init() { x = 123456789, y = 362436069, z = 521288629, w = 88675123; } int operator()() { unsigned t = (x^(x<<11)); x = y; y = z; z = w; w = (w ^ (w>>19)) ^ (t ^ (t>>8)); return (int)w; } private: unsigned x, y, z, w; }; #ifdef __WATCOMC__ // open watcom c++ (1.8)では未実装だったようなので, merge_sortで代用. #define stable_sort merge_sort #endif #ifdef __WATCOMC__ // open watcom c++ (1.8)では未実装だったのでようなので、代用品を用意. #define upper_bound Upper_Bound // std::upper_bound の置換 template <typename FwdIte, class T, class C> FwdIte Upper_Bound(FwdIte first, FwdIte last, const T& val, C cmp) { std::ptrdiff_t size = std::distance(first, last); if (size > 0) { FwdIte mid = first; do { std::ptrdiff_t half_size = size >> 1; std::advance(mid, half_size); if (cmp(val, *mid)) { size = half_size; mid = first; } else { ++mid; first = mid; size = size - half_size - 1; } } while (size > 0); } return first; } #endif // =========================================================================== // テストのソート対象の型関係 // TYPE : このテストでのソート対象の型 // TYPE_SMPCLASS : 0=SmpClass外 1={key_,no_}のみ(8bytes) 2=SmpClass* (4bytes) 3=SmpClass自身(128bytes) となる. #ifdef TYPE_SMPCLASS // サンプルクラスをソート対象にする場合. class SmpClass { public: SmpClass(float key=0, unsigned no=0) : key_(key), no_(no) { #if TYPE_SMPCLASS > 1 memset(rsv_,0,sizeof rsv_); #endif } const bool operator==(const SmpClass& r) const { return key_ == r.key_; } #if TYPE_SMPCLASS == 4 // ※ no_込みでquick_sortする場合用. const bool operator< (const SmpClass& r) const { return val() < r.val(); } unsigned long long val() const { return ((unsigned long long)(*(unsigned*)&key_) << 32) | no_; } #else const bool operator< (const SmpClass& r) const { return key_ < r.key_; } //const bool operator< (const SmpClass& r) const { return val_bin() < r.val_bin(); } float val() const { return key_; } #endif unsigned val_bin() const { return *(unsigned*)&key_; } unsigned no() const { return no_; } // 同一値のときの登録順番チェック用. #if 1 SmpClass(const SmpClass& r) : key_(r.key_), no_(r.no_) { #if TYPE_SMPCLASS > 1 memcpy(rsv_,r.rsv_,sizeof rsv_); #endif } void swap(SmpClass& r) { std::swap(key_,r.key_); std::swap(no_, r.no_); #if TYPE_SMPCLASS > 1 for (unsigned i = 0; i < sizeof(rsv_)/sizeof(rsv_[0]); ++i) std::swap(rsv_[i], r.rsv_[i]); #endif } SmpClass& operator=(const SmpClass& r) { SmpClass(r).swap(*this); return *this; } #endif private: float key_; // 比較で用いる値. unsigned no_; // 登録番号. 安定ソートのチェックに使う. #if TYPE_SMPCLASS == 4 // ※ no_込みでquick_sortする場合用. unsigned rsv_[1]; // 本来は何か処理用のメンバー変数. #elif TYPE_SMPCLASS > 1 // ※ 1の時は key_,no_のみとして扱う. unsigned rsv_[32-1-1]; // 本来は何か処理用のメンバー変数. #endif }; //namespace std { template<> inline void swap<SmpClass>(SmpClass& l, SmpClass& r) { l.swap(r); } } inline void swap(SmpClass& l, SmpClass& r) { l.swap(r); } class SmpClassMgr { public: SmpClassMgr() : no_(0) {} SmpClass& add(float key) { list_.push_back(SmpClass(key, newNo())); return list_.back(); } void init() { list_.clear(); } void term() { list_.clear(); } unsigned newNo() { return no_++; } private: std::list<SmpClass> list_; unsigned no_; }; SmpClassMgr g_smpClassMgr; // #if TYPE_SMPCLASS == 2 // クラスへのポインタをソートするとき #define TYPE SmpClass* #else #define TYPE SmpClass #endif #endif // SmpClass を使わない場合 #ifdef TYPE_DOUBLE #define TYPE double #endif #ifdef TYPE_INT #define TYPE int #endif #ifndef TYPE #error TYPEが未指定. #endif // =========================================================================== // ソート用の比較処理. #if TYPE_SMPCLASS == 2 // 要素がポインタの時用.(実体が小なり) template<typename T> struct Cmp { bool operator()(const T& l, const T& r) const { return *l < *r; } }; #else // ポインタ以外なら 小なり、で比較 #define Cmp std::less #endif // =========================================================================== // 各ソートのテスト.（ソートルーチンの呼び出しを統一するためのワンクッション) #define TEST_SORT_TBL_N(name) \ template<typename T> \ struct test_##name { \ void run(T* data, size_t size) { \ name(data, size, Cmp<T>()); \ } \ } TEST_SORT_TBL_N(bubble_sort); TEST_SORT_TBL_N(selection_sort); TEST_SORT_TBL_N(insertion_sort); TEST_SORT_TBL_N(insertion_sort_y); TEST_SORT_TBL_N(insertion_sort_y_mod); TEST_SORT_TBL_N(shell_sort); TEST_SORT_TBL_N(comb_sort); TEST_SORT_TBL_N(comb_sort11); TEST_SORT_TBL_N(simple_quick_sort); #ifdef USE_QSORT TEST_SORT_TBL_N(c_qsort); #endif #define TEST_SORT_BGN_END(name) \ template<typename T> \ struct test_##name { \ void run(T* data, size_t size) { \ name(data, data+size, Cmp<T>()); \ } \ } TEST_SORT_BGN_END(sort); // std::sort TEST_SORT_BGN_END(stable_sort); // std::stable_sort TEST_SORT_BGN_END(quick_sort); TEST_SORT_BGN_END(quick_sort_y); TEST_SORT_BGN_END(merge_sort); // 基数ソートのためのソートキー取得. #ifdef TYPE_SMPCLASS template<typename T> struct smpclassptr_radix_sort_getkey : public std::unary_function<T, unsigned> { unsigned operator()(const T& p) const { #if TYPE_SMPCLASS == 2 // pointerのとき. return p->val_bin(); #else return p.val_bin(); #endif } }; #endif // 基数ソートのテスト. template<typename T> struct test_radix_sort { void run(T* data, size_t size) { #ifdef TYPE_SMPCLASS radix_sort<8>( data, size, smpclassptr_radix_sort_getkey<T>() ); #elif defined TYPE_INT radix_sort<8>( data, size, radix_sort_ofsaddr_getkey<unsigned, int, 0>() ); #elif defined TYPE_DOUBLE radix_sort<8>( data, size, radix_sort_ofsaddr_getkey<unsigned long long, double, 0>() ); #else #error コンパイル設定がおかしい. #endif } }; #ifdef CHECK_STABLE // 安定ソートチェックでは値を0〜255に限定しているのでビンソートも試してみる. template<typename T> struct test_backet_sort { void run(T* data, size_t size) { backet_sort( data, size, T(0), T(255) ); } }; #endif // upper_boundを用いて安定ソート状態を維持しながら、値をvectorに挿入した結果をコピー. template<typename T> struct test_vec_insert { void run(T* data, size_t size) { std::vector<T> tbl; tbl.reserve(size); tbl.push_back(data[0]); for (unsigned i = 1; i < size; ++i) { tbl.insert( upper_bound(tbl.begin(), tbl.end(), data[i], Cmp<T>()), data[i] ); } std::copy(tbl.begin(), tbl.end(), data); } }; // multisetへ値を挿入してその結果をコピー. template<typename T> struct test_multiset_insert { void run(T* data, size_t size) { std::multiset<T, Cmp<T> > tbl; for (unsigned i = 0; i < size; ++i) { tbl.insert( data[i] ); } std::copy(tbl.begin(), tbl.end(), data); } }; // =========================================================================== // 計測＆チェック template<typename T, class SortFunc> double benchmark(SortFunc sortFunc, size_t size, size_t count, unsigned flags, const char* ttl) { unsigned char stableFlag = (flags & 1); unsigned char verboss = (flags & 2); T* data = new T[ size * count + 16 ]; if (data == 0) { printf("not enough memory.\n"); exit(1); } if (verboss) fprintf(stderr, "\t%s:start\n", ttl); #if TYPE_SMPCLASS == 2 // SmpClass*のとき. g_smpClassMgr.init(); #endif // ソート対象のデータを作成. Rand_XorShift rnd; for (unsigned i = 0; i < size * count; ++i) { #if defined CHECK_STABLE // stableのチェックのときは unsigned r = (unsigned)rnd() >> 24; // 値を0〜255にして同一値の数を増やす. #else unsigned r = (unsigned)rnd() >> 1; // 基数ソートの比較を楽にするため負数無し. #endif // 乱数で初期化. #if TYPE_SMPCLASS == 2 data[i] = &g_smpClassMgr.add( r ); #elif TYPE_SMPCLASS > 0 data[i] = T( r, g_smpClassMgr.newNo() ); #else data[i] = T( r ); #endif //printf("%s : %d : %8x\n", ttl, i, data[i]); } // ソート時間の計測. unsigned ofs = 0; PerfCnt_tick_t start_time = PerfCnt_getTick(); // 計測開始 for (unsigned j = 0; j < count; ++j) { sortFunc.run(&data[ofs], size); // ソート中 ofs += size; } PerfCnt_tick_t elapsed = PerfCnt_getTick() - start_time; // 計測終了 #if 1 // 大小関係があっているかをチェック. bool err = false; unsigned stable_chk_count = 0; Cmp<T> cmp; ofs = 0; for (unsigned j = 0; j < count; ++j) { static int err_cnt = 0; for (unsigned i = 0; i < size-1; ++i) { // printf("%d : %d : %d : %8x, %8x\n", algoNo, j, i, data[i], data[i+1]); if (cmp(data[ofs+i+1] , data[ofs+i])) { printf("%s : <%d> [%d] : error\n", ttl, j, i); ++err_cnt; } #if defined TYPE_SMPCLASS && defined CHECK_STABLE // 同一値の時、登録順になっているかをチェック. #if TYPE_SMPCLASS == 2 // 生ポインタ版の時の同一チェック. else if (stableFlag && *data[ofs+i] == *data[ofs+i+1]) #else // ポインタクラス版の時の同一チェック. else if (stableFlag && data[ofs+i] == data[ofs+i+1]) #endif { ++stable_chk_count; #if TYPE_SMPCLASS == 2 // 生ポインタ版の時の同一チェック. if (data[ofs+i]->no() >= data[ofs+i+1]->no()) #else if (data[ofs+i].no() >= data[ofs+i+1].no()) #endif { printf("%s : <%d> [%d] : not stable\n", ttl, j, i); ++err_cnt; } } #endif } if (err_cnt >= 100) { printf("too many errors.\n"); err = 1; break; // exit(1); } ofs += size; } #if 0 //defined TYPE_SMPCLASS && defined CHECK_STABLE if (stableFlag) { printf("%s : stable_chk_count = %d\n", ttl, stable_chk_count); } #endif #endif #if TYPE_SMPCLASS == 2 // SmpClass*のとき. g_smpClassMgr.term(); #endif delete[] data; double e = elapsed * 1.0 / (PerfCnt_tickPerSec()*count); if (err) e = 0; if (verboss) fprintf(stderr, "\t%s:end (%f)\n", ttl, e * 1000000.0); return e; // ソート時間. } // =========================================================================== int main(int argc, char* argv[]) { struct St { size_t size; size_t count; double elaped[32]; }; St st[] = { { 10,10000, }, { 20, 5000, }, { 30, 3333, }, { 40, 2500, }, { 50, 2000, }, { 64, 1562, }, { 100, 1000, }, { 128, 781, }, { 256, 390, }, { 512, 195, }, { 1024, 98, }, { 10000, 10, }, { 100000, 1, }, { 1000000, 1, }, { 10000000, 1, }, {100000000, 1, }, }; enum { tblSz = 32 }; const char* nm[tblSz] = {0}; bool bFastType = 0; unsigned n = sizeof(st) / sizeof(st[0]); unsigned n_low = 13; // 100000 unsigned v = 0; // 状況で実行回数を微調整. --n; if (sizeof(TYPE) > 4) // 大き目のソートならチェックを減らす. --n_low; #if TYPE_SMPCLASS >= 2 // SmpClassは比較が重めになるのでチェック減らす. --n; --n_low; #endif unsigned mul = 1; // オプションチェック for (int i = 1; i < argc; ++i) { if (strcmp(argv[i], "-low") == 0) { // 低スペックでの実行用. n -= 1; n_low -= 1; } else if (strcmp(argv[i], "-high") == 0) { // 高スペック環境の場合. ++n; } else if (strcmp(argv[i], "-v") == 0) { // verboss. v = 2; } else if (strncmp(argv[i], "-m",2) == 0) { // 回数をm倍する. mul = strtol(argv[i]+2,0,0); if (mul < 1) mul = 1; } else if (strcmp(argv[i], "-fast") == 0) { // 手っ取り早く、速いアルゴリズムのみ試す. bFastType = 1; } } // SJIS \ 問題回避で ソートをSORT に置換. fprintf(stderr, "\n%s (%dbytes) の SORT テスト\n", MAC_STR(TYPE), sizeof(TYPE) ); // 各ソートのチェック. for (unsigned i = 0; i < n; ++i) { St* t = &st[i]; unsigned count = t->count * mul; if (v) fprintf(stderr, "個数 %9d, 処理回数 %9d\n", t->size, count); unsigned k = 0; if (i < n_low && !bFastType) { nm[k] = "バブル SORT "; t->elaped[k] = benchmark<TYPE>(test_bubble_sort<TYPE>() , t->size, count, 0|v, nm[k]); ++k; // nm[k] = "選択 SORT "; t->elaped[k] = benchmark<TYPE>(test_selection_sort<TYPE>() , t->size, count, 0|v, nm[k]); ++k; nm[k] = "挿入 SORT "; t->elaped[k] = benchmark<TYPE>(test_insertion_sort<TYPE>() , t->size, count, 1|v, nm[k]); ++k; nm[k] = "挿入 SORT (yane) "; t->elaped[k] = benchmark<TYPE>(test_insertion_sort_y<TYPE>() , t->size, count, 1|v, nm[k]); ++k; // nm[k] = "挿入 SORT (y改) "; t->elaped[k] = benchmark<TYPE>(test_insertion_sort_y_mod<TYPE>() , t->size, count, 1|v, nm[k]); ++k; } k = 5; { nm[k] = "シェル SORT "; t->elaped[k] = benchmark<TYPE>(test_shell_sort<TYPE>() , t->size, count, 0|v, nm[k]); ++k; nm[k] = "コム SORT "; t->elaped[k] = benchmark<TYPE>(test_comb_sort<TYPE>() , t->size, count, 0|v, nm[k]); ++k; // nm[k] = "コム SORT 11 "; t->elaped[k] = benchmark<TYPE>(test_comb_sort11<TYPE>() , t->size, count, 0|v, nm[k]); ++k; nm[k] = "QUICK SORT(単純) "; t->elaped[k] = benchmark<TYPE>(test_simple_quick_sort<TYPE>() , t->size, count, 0|v, nm[k]); ++k; } k = 9; { nm[k] = "QUICK SORT(+挿入) "; t->elaped[k] = benchmark<TYPE>(test_quick_sort<TYPE>() , t->size, count, 0|v, nm[k]); ++k; nm[k] = "QUICK SORT(+yane) "; t->elaped[k] = benchmark<TYPE>(test_quick_sort_y<TYPE>() , t->size, count, 0|v, nm[k]); ++k; nm[k] = "std::sort "; t->elaped[k] = benchmark<TYPE>(test_sort<TYPE>() , t->size, count, 0|v, nm[k]); ++k; nm[k] = "std::stable_sort "; t->elaped[k] = benchmark<TYPE>(test_stable_sort<TYPE>() , t->size, count, 1|v, nm[k]); ++k; nm[k] = "マージ SORT "; t->elaped[k] = benchmark<TYPE>(test_merge_sort<TYPE>() , t->size, count, 1|v, nm[k]); ++k; nm[k] = "基数 SORT "; t->elaped[k] = benchmark<TYPE>(test_radix_sort<TYPE>() , t->size, count, 1|v, nm[k]); ++k; } k = 16; if (i < n_low+1 && !bFastType) { nm[k] = "multiset insert "; t->elaped[k] = benchmark<TYPE>(test_multiset_insert<TYPE>() , t->size, count, 0|v, nm[k]); ++k; } k = 17; if (i < n_low && count <= 100000 && !bFastType) { nm[k] = "vector insert "; t->elaped[k] = benchmark<TYPE>(test_vec_insert<TYPE>() , t->size, count, 1|v, nm[k]); ++k; } #ifdef USE_QSORT k = 18; if (!bFastType) { nm[k] = "c qsort "; t->elaped[k] = benchmark<TYPE>(test_c_qsort<TYPE>() , t->size, count, 0|v, nm[k]); ++k; } #endif #if defined CHECK_STABLE && defined TYPE_INT // 安定ソートチェックでは値を0〜255に限定しているのでビンソートも試してみる. k = 19; { nm[k] = "BACKET SORT "; t->elaped[k] = benchmark<TYPE>(test_backet_sort<TYPE>() , t->size, count, 1|v, nm[k]); ++k; } #endif } // 実行結果の出力 printf("\n*** %s (%dbytes) の SORT テスト\n", MAC_STR(TYPE), sizeof(TYPE) ); printf("\n"); printf(",%18s ,", "個数"); for (unsigned i = 0; i < n; ++i) { printf("%10d個,", st[i].size); }; printf("\n"); printf(",%18s ,", "回数(結果は平均)"); for (unsigned i = 0; i < n; ++i) { printf(" (%5d回),", st[i].count*mul); }; printf("\n"); for (unsigned j = 0; j < tblSz; ++j) { if (nm[j] == 0) continue; printf(",%-18s ,", nm[j]); for (unsigned i = 0; i < n; ++i) { double e = st[i].elaped[j]*1000000.0; if (e > 0) printf("%12.3f,", e); else printf("%12s,", "---"); } printf("\n"); } printf("\n"); return 0; }