1 : // ソートテスト その３ : list データのソート.
    2 : #include <stdio.h>
    3 : #include <stdlib.h>
    4 : #include <time.h>
    5 : #include <assert.h>
    6 : #include <algorithm>
    7 : #include <functional>
    8 : #include <vector>
    9 : #include <list>
   10 : #include <string>
   11 : 
   12 : 
   13 : template<typename BidiIte, class C >
   14 : void bidi_quick_sort(BidiIte first, BidiIte last, C cmp )
   15 : {
   16 :     typedef typename std::iterator_traits<BidiIte>::value_type  T;
   17 : 
   18 :     using std::iter_swap;
   19 :     std::size_t size = std::size_t(std::distance(first, last));
   20 :     if (size <= 32) {
   21 :         if (size <= 1)
   22 :             return;
   23 :         BidiIte i = first;
   24 :         while (++i != last) {
   25 :             T       tmp( *i );
   26 :             BidiIte j = i;
   27 :             BidiIte k = i;
   28 :             do {
   29 :                 --k;
   30 :                 if (!cmp(tmp, *k))
   31 :                     break;
   32 :                 *j = *k;
   33 :                 --j;
   34 :             } while (k != first);
   35 :             *j = tmp;
   36 :         }
   37 :         return;
   38 :     }
   39 :     BidiIte ite( first );
   40 :     std::advance( ite, size / 2 );
   41 :     const T m( *ite );
   42 :     BidiIte     l = first;
   43 :     BidiIte     r = last;
   44 :     std::size_t lc = 0;
   45 :     std::size_t rc = size;
   46 :     for (;;) {
   47 :         while (cmp(*l, m))
   48 :             ++l, ++lc;
   49 :         do {
   50 :             --r, --rc;
   51 :         } while (cmp(m, *r));
   52 :         if (lc >= rc)
   53 :             break;
   54 :         iter_swap(l, r);
   55 :         ++l, ++lc;
   56 :     }
   57 :     bidi_quick_sort(first, l   , cmp);
   58 :     bidi_quick_sort(l    , last, cmp);
   59 : }
   60 : 
   61 : 
   62 : 
   63 : template<typename BidiIte> inline
   64 : void bidi_quick_sort(BidiIte first, BidiIte last) {
   65 :     bidi_quick_sort( first, last, std::less<typename std::iterator_traits<BidiIte>::value_type>() );
   66 : }
   67 : 
   68 : 
   69 : 
   70 : // ===========================================================================
   71 : #ifdef _WIN32
   72 : #include <windows.h>
   73 : typedef unsigned __int64 PerfCnt_tick_t;
   74 : PerfCnt_tick_t PerfCnt_getTick()    { PerfCnt_tick_t c; QueryPerformanceCounter((LARGE_INTEGER*)&c); return c; }
   75 : PerfCnt_tick_t PerfCnt_tickPerSec() { static PerfCnt_tick_t s = 0; if (!s) QueryPerformanceFrequency((LARGE_INTEGER*)&s); return s; }
   76 : #else
   77 : #include <time.h>
   78 : typedef clock_t PerfCnt_tick_t;
   79 : #define PerfCnt_getTick()           clock()
   80 : #define PerfCnt_tickPerSec()        CLOCKS_PER_SEC
   81 : #endif
   82 : 
   83 : 
   84 : 
   85 : // ===========================================================================
   86 : 
   87 : template<typename T>
   88 : T random() {
   89 :     return T(rand());
   90 : }
   91 : 
   92 : template<>
   93 : std::string random<std::string>() {
   94 :     char buf[128];
   95 :     sprintf(buf, "%d%d%d", rand(),rand(),rand());
   96 :     return std::string(buf);
   97 : }
   98 : 
   99 : 
  100 : 
  101 : // ===========================================================================
  102 : #ifdef USE_SMPCLASS
  103 : #if USE_SMPCLASS != 1
  104 : #include <tr1/array>
  105 : #endif
  106 : 
  107 : class SmpClass {
  108 : public:
  109 :     ~SmpClass() { free(name_); }
  110 :     SmpClass() : name_(0), x_(0),y_(0),z_(0),argb_(0xFFFFFFFF),mode_(0) { /*buf_.resize(256);*/ }
  111 : 
  112 :     SmpClass(const SmpClass& r)
  113 :         : name_(strdup(r.name_)), x_(r.x_), y_(r.y_), z_(r.z_), argb_(r.argb_), mode_(r.mode_), buf_(r.buf_) {}
  114 : 
  115 :     SmpClass(const char* name, double x, double y, double z, unsigned argb=0xffffffff, unsigned mode=0)
  116 :         : name_(strdup(name)), x_(x), y_(y), z_(z), argb_(argb), mode_(mode)
  117 :     {
  118 :       #if USE_SMPCLASS == 1
  119 :         buf_.resize(256);
  120 :       #endif
  121 :     }
  122 : 
  123 :     SmpClass& operator=(const SmpClass& r) { SmpClass(r).swap( *this ); return *this; }
  124 : 
  125 :     void swap(SmpClass& r);
  126 :     bool operator<(const SmpClass& r) const;
  127 : 
  128 : private:
  129 :     char*                       name_;
  130 :     double                      x_, y_, z_;
  131 :     unsigned                    argb_;
  132 :     unsigned                    mode_;
  133 :   #if USE_SMPCLASS == 1
  134 :     std::vector<char>           buf_;
  135 :   #else
  136 :     std::tr1::array<char,160>   buf_;
  137 :   #endif
  138 : };
  139 : 
  140 : 
  141 : inline void SmpClass::swap(SmpClass& r) {
  142 :     using std::swap;
  143 :     swap(name_, r.name_);
  144 :     swap(x_   , r.x_   );
  145 :     swap(y_   , r.y_   );
  146 :     swap(z_   , r.z_   );
  147 :     swap(argb_, r.argb_);
  148 :     swap(mode_, r.mode_);
  149 :     swap(buf_ , r.buf_ );
  150 : }
  151 : 
  152 : 
  153 : inline bool SmpClass::operator<(const SmpClass& r) const {
  154 :     if (z_ < r.z_)
  155 :         return 1;
  156 :     if (z_ > r.z_)
  157 :         return 0;
  158 :     if (y_ < r.y_)
  159 :         return 1;
  160 :     if (y_ > r.y_)
  161 :         return 0;
  162 :     return strcmp(name_, r.name_) < 0;
  163 : }
  164 : 
  165 : 
  166 : template<>
  167 : SmpClass random<SmpClass>() {
  168 :     char name[128];
  169 :     sprintf(name, "%c%c%d", 'A'+rand()%26,'a'+rand()%26,'a'+rand()%26, rand());
  170 :     return SmpClass(name, rand(), rand(), rand());
  171 : }
  172 : 
  173 : 
  174 : #define TYPE        SmpClass
  175 : #endif
  176 : 
  177 : 
  178 : 
  179 : // ===========================================================================
  180 : 
  181 : template<typename T>
  182 : double benchmark1(unsigned size, unsigned count, int seed=1) {
  183 :     srand(seed);
  184 :     PerfCnt_tick_t  elapsed = 0;
  185 :     for (unsigned j = 0; j < count; ++j) {
  186 :         std::vector<T> data;
  187 :         data.reserve(size);
  188 :         for (unsigned i = 0; i < size; ++i)
  189 :             data.push_back(random<T>());
  190 :         PerfCnt_tick_t  start_time = PerfCnt_getTick();
  191 :         bidi_quick_sort(data.begin(), data.end() );
  192 :         elapsed    += PerfCnt_getTick() - start_time;
  193 :     }
  194 :     return elapsed / double(PerfCnt_tickPerSec() * count);
  195 : }
  196 : 
  197 : 
  198 : template<typename T>
  199 : double benchmark2(unsigned size, unsigned count, int seed=1) {
  200 :     srand(seed);
  201 :     PerfCnt_tick_t  elapsed = 0;
  202 :     for (unsigned j = 0; j < count; ++j) {
  203 :         std::list<T> data;
  204 :         for (unsigned i = 0; i < size; ++i)
  205 :             data.push_back(random<T>());
  206 :         PerfCnt_tick_t  start_time = PerfCnt_getTick();
  207 :         bidi_quick_sort( data.begin(), data.end() );
  208 :         elapsed    += PerfCnt_getTick() - start_time;
  209 :     }
  210 :     return elapsed / double(PerfCnt_tickPerSec() * count);
  211 : }
  212 : 
  213 : 
  214 : template<typename T>
  215 : double benchmark3(unsigned size, unsigned count, int seed=1) {
  216 :     srand(seed);
  217 :     PerfCnt_tick_t  elapsed = 0;
  218 :     for (unsigned j = 0; j < count; ++j) {
  219 :         std::list<T> data;
  220 :         for (unsigned i = 0; i < size; ++i)
  221 :             data.push_back(random<T>());
  222 :         PerfCnt_tick_t  start_time = PerfCnt_getTick();
  223 :         data.sort();
  224 :         elapsed    += PerfCnt_getTick() - start_time;
  225 :     }
  226 :     return elapsed / double(PerfCnt_tickPerSec() * count);
  227 : }
  228 : 
  229 : 
  230 : template<typename T>
  231 : struct ptr_less {
  232 :     bool operator()(T l, T r) const {
  233 :         return *l < *r;
  234 :     }
  235 : };
  236 : 
  237 : 
  238 : template<typename T>
  239 : double benchmark4(unsigned size, unsigned count, int seed=1) {
  240 :     srand(seed);
  241 :     PerfCnt_tick_t  elapsed = 0;
  242 :     for (unsigned j = 0; j < count; ++j) {
  243 :         std::list<T> data;
  244 :         for (unsigned i = 0; i < size; ++i)
  245 :             data.push_back(random<T>());
  246 : 
  247 :         PerfCnt_tick_t  start_time = PerfCnt_getTick();
  248 :         std::vector<T*> ent(size);
  249 :         typename std::vector<T*>::iterator vi = ent.begin();
  250 :         for (typename std::list<T>::iterator li = data.begin(); li != data.end(); ++li) {
  251 :             *vi = &*li;
  252 :             ++vi;
  253 :         }
  254 :         bidi_quick_sort(ent.begin(), ent.end(), ptr_less<T*>() );
  255 :         elapsed    += PerfCnt_getTick() - start_time;
  256 :     }
  257 :     return elapsed / double(PerfCnt_tickPerSec() * count);
  258 : }
  259 : 
  260 : 
  261 : 
  262 : 
  263 : #ifndef TYPE
  264 : #define TYPE    int
  265 : #endif
  266 : 
  267 : struct St {
  268 :     size_t      size;
  269 :     size_t      count;
  270 :     double      elaped[4];
  271 : };
  272 : 
  273 : 
  274 : //
  275 : int main(int argc, char **argv) {
  276 :     if (argc < 2) {
  277 :         printf("usage> sort_test3 size1 count1 [size2 count2 ...]\n");
  278 :         return 1;
  279 :     }
  280 :     std::vector<St> st;
  281 :     unsigned n = 0;
  282 :     for (unsigned i = 1; i < argc; i += 2) {
  283 :         St  t;
  284 :         t.size   = atoi(argv[i]);
  285 :         t.count  = (i+1 < argc) ? atoi(argv[i+1]) : 1;
  286 :         std::fill(t.elaped, t.elaped+4, 0.0);
  287 :         st.push_back(t);
  288 :         ++n;
  289 :     }
  290 : 
  291 :     printf("\nsort_test3 : sizeof(TYPE)=%dbytes\n", sizeof(TYPE));
  292 :     int    seed  = 1; //time(0);
  293 :     for (unsigned i = 0; i < n; ++i) {
  294 :         St& t = st[i];
  295 :         printf("個数 %9d, 処理回数 %9d\n", t.size, t.count);
  296 :         t.elaped[0] = benchmark1<TYPE>(t.size, t.count, seed);
  297 :         t.elaped[1] = benchmark2<TYPE>(t.size, t.count, seed);
  298 :         t.elaped[2] = benchmark3<TYPE>(t.size, t.count, seed);
  299 :         t.elaped[3] = benchmark4<TYPE>(t.size, t.count, seed);
  300 :     }
  301 : 
  302 :     // 結果表示.
  303 :     static const char* ttl[] = {
  304 :         "vectorを quick sort               ",
  305 :         "list  を quick sort               ",
  306 :         "std::list.sort                    ",
  307 :         "list要素へのポインタのvectorをsort",
  308 :         NULL,
  309 :     };
  310 :     printf("\n");
  311 :     printf("%34s ,", "個数");
  312 :     for (unsigned i = 0; i < n; ++i) {
  313 :         printf("%9d個,", st[i].size);
  314 :     };
  315 :     printf("\n");
  316 :     for (unsigned j = 0; ttl[j]; ++j) {
  317 :         printf("%-34s ,", ttl[j]);
  318 :         for (unsigned i = 0; i < n; ++i) {
  319 :             printf("%11.3f,", st[i].elaped[j]*1000000.0);
  320 :         };
  321 :         printf("\n");
  322 :     }
  323 :     return 0;
  324 : }