fork(1) download 
  1. #if _MSC_VER
  2. #pragma warning(disable: 4996) // _CRT_SECURE_NO_WARNINGS
  3. #include <intrin.h>
  4. #else
  5.  
  6. #include <x86intrin.h>
  7. #endif
  8.  
  9. #include <stdio.h>
  10. #include <string.h>
  11. #include <iostream>
  12. #include <vector>
  13. #include <array>
  14. #include <type_traits>
  15. #include <algorithm>
  16. #include <random>
  17. #include <cmath>
  18. #include <typeinfo>
  19.  
  20. #ifndef SYS_BITS
  21. #define CHAR_BITS 8
  22. #define SYS_BYTES sizeof(std::size_t)
  23. #define SYS_BITS (SYS_BYTES * CHAR_BITS)
  24. #endif
  25.  
  26. #define min_(a,b) ( (a) < (b) ? (a) : (b))
  27. #define FUN(function_name) #function_name, function_name
  28. #define as_array( ptr, size ) ( *(std::array< std::remove_reference< decltype( *ptr ) >::type, size >*)ptr )
  29.  
  30. using SOURCE = short;
  31. using RESULT = SOURCE;
  32. using DISTRIBUTION_SOURCE = double;
  33. using ON_RUN = void(&)(void*);
  34. using ON_PREPARE = void(&)(void*);
  35. using ON_COMPARE = bool(&)(void*, void*, std::size_t);
  36.  
  37. SOURCE src[1 << 11];
  38. constexpr std::size_t SIZE = sizeof src / sizeof *src;
  39. RESULT dst0[SIZE], dst1[SIZE], dst2[SIZE], dst3[SIZE], dst4[SIZE];
  40.  
  41. void Prepare(void* _result)
  42. {
  43.     memcpy(_result, src, sizeof src);
  44. }
  45.  
  46. bool Compare(void* _result, void* _answer, std::size_t _bytes)
  47. {
  48.     return memcmp(_result, _answer, _bytes) == 0;
  49. }
  50.  
  51. class RUNNER
  52. {
  53.     friend class BENCH;
  54. private:
  55.     const char* name;
  56.     unsigned long long elapsed;
  57.     const ON_RUN onRun;
  58.     void* result;
  59.  
  60.     RUNNER(const char* _name, ON_RUN& _onRun, void* _result)
  61.         : name(_name)
  62.         , onRun(_onRun)
  63.         , elapsed(-1)
  64.         , result(_result)
  65.     {
  66.  
  67.     }
  68.  
  69.     void Run()
  70.     {
  71.         auto begin = __rdtsc();
  72.         onRun(result);
  73.         elapsed = min_(elapsed, __rdtsc() - begin);
  74.     }
  75. };
  76.  
  77. class BENCH
  78. {
  79. private:
  80.     const char* title;
  81.     const unsigned int trial;
  82.     ON_PREPARE onPrepare;
  83.     ON_COMPARE onCompare;
  84.  
  85.     std::vector< RUNNER*> runners;
  86.     std::size_t answerSize;
  87.     void* answer;
  88. public:
  89.     BENCH(const char* _title, const int _trial, ON_PREPARE&& _onPrepare, ON_COMPARE& _onCompare)
  90.         : title(_title)
  91.         , trial(_trial)
  92.         , onPrepare(_onPrepare)
  93.         , onCompare(_onCompare)
  94.     {
  95.  
  96.     }
  97.  
  98.     ~BENCH()
  99.     {
  100.         for (auto runner : runners)
  101.         {
  102.             delete[] runner;
  103.         }
  104.         runners.clear();
  105.     }
  106.  
  107.     auto Record(unsigned int index) const
  108.     {
  109.         return runners[index]->elapsed;
  110.     }
  111.  
  112.     auto RunnerCount() const
  113.     {
  114.         return runners.size();
  115.     }
  116.  
  117.     void Solution(ON_RUN&& _correctFunction, void* _result, const std::size_t _bytes)
  118.     {
  119.         answer = _result;
  120.         answerSize = _bytes;
  121.         onPrepare(_result);
  122.         _correctFunction(_result);
  123.     }
  124.  
  125.     template<typename T>
  126.     void PenzerDebug(T& _result)
  127.     {
  128.         printf("\nPenzer's debug log - DataType: %s\n", typeid(_result).name());
  129.     }
  130.  
  131.     template<typename T>
  132.     void Solution(ON_RUN& _correctFunction, T& _result, const std::size_t _bytes)
  133.     {
  134.         PenzerDebug(_result);
  135.         Solution(_correctFunction, &_result, _bytes);
  136.     }
  137.  
  138.     void Add(const char* _name, ON_RUN& _onRun, void* _result)
  139.     {
  140.         runners.emplace_back(new RUNNER(_name, _onRun, _result));
  141.     }
  142.  
  143.     template<typename T>
  144.     void Add(const char* _name, ON_RUN& _onRun, T& _result)
  145.     {
  146.         Add(_name, _onRun, &_result);
  147.     }
  148.  
  149.     void run() const
  150.     {
  151.         if (runners.empty())
  152.         {
  153.             return;
  154.         }
  155.  
  156.         printf("\n   < %d bits %d trial >    %s\n", (int)SYS_BITS, trial, title);
  157.         puts("   ----------------+---------------------------------+-----------------------");
  158.         puts("   |    CHECKER    |          function name          |    minimum clocks    |");
  159.         puts("   ----------------+---------------------------------+-----------------------");
  160.  
  161.         unsigned long long minClocks = -1;
  162.         unsigned long long maxClocks = 0;
  163.         unsigned long long penzerClocks = 0;
  164.         unsigned long long bossClocks = 0;
  165.  
  166.         RUNNER* minRunner = runners[0];
  167.         RUNNER* maxRunner = runners[0];
  168.  
  169.         for (const auto runner : runners)
  170.         {
  171.             int passCount = 0;
  172.             for (unsigned int i = 0; i < trial; i++)
  173.             {
  174.                 onPrepare(runner->result);
  175.                 runner->Run();
  176.                 passCount += onCompare(runner->result, answer, answerSize);
  177.             }
  178.  
  179.             if (runner->name == "BOSS::run")
  180.             {
  181.                 bossClocks = runner->elapsed;
  182.             }
  183.  
  184.             if (runner->name == "PENZER::run")
  185.             {
  186.                 penzerClocks = runner->elapsed;
  187.             }
  188.  
  189.             if (minClocks > runner->elapsed)
  190.             {
  191.                 minRunner = runner;
  192.                 minClocks = runner->elapsed;
  193.             }
  194.             if (maxClocks < runner->elapsed)
  195.             {
  196.                 maxRunner = runner;
  197.                 maxClocks = runner->elapsed;
  198.             }
  199.  
  200.             char temp[14];
  201.             if (trial == passCount)
  202.             {
  203.                 sprintf(temp, "       PASSED");
  204.             }
  205.             else
  206.             {
  207.                 sprintf(temp, "FAILED%7d", trial - passCount);
  208.             }
  209.  
  210.             printf("   [ %s ] %32s %15llu clocks\n", temp, runner->name, runner->elapsed);
  211.         }
  212.         puts("   --------------------------------------------------------------------------");
  213.         if (penzerClocks < bossClocks)
  214.         {
  215.             printf("   PENZER is faster than BOSS  ( %.2f times faster )\n\n", float(bossClocks) / penzerClocks);
  216.         }
  217.         else
  218.         {
  219.             printf("   BOSS is faster than PENZER  ( %.2f times faster )\n\n", float(penzerClocks) / bossClocks);
  220.         }
  221.  
  222.     }
  223. };
  224.  
  225. namespace BOSS
  226. {
  227.  
  228.     void run(void* dst)
  229.     {
  230.         auto&   arr = as_array((SOURCE*)dst, SIZE);
  231.         std::sort(arr.begin(), arr.end());
  232.     }
  233.  
  234. };
  235. //------------------------------+---------------------------------------------------------------
  236.  
  237. namespace PENZER
  238. {
  239.  
  240. #include <cstdlib>
  241. #define SAFE_DELETE_ARRAY(p) if(p != nullptr) delete[] p; p = nullptr;
  242.  
  243.     enum RADIX_TYPE
  244.     {
  245.         RT_8BIT = 0,
  246.         RT_16BIT,
  247.         RT_MAX
  248.     };
  249.  
  250.     constexpr int g_insertKeyValue = 1 << 6;
  251.  
  252.  
  253.     const int Log2(const int N)
  254.     {
  255.         return (N > 1) ? (1 + Log2(N >> 1)) : 0;
  256.     }
  257.  
  258.     const int Max(const int first, const int second)
  259.     {
  260.         return (first > second) ? first : second;
  261.     }
  262.  
  263.     const int Min(const int first, const int second)
  264.     {
  265.         return (first < second) ? first : second;
  266.     }
  267.  
  268.     template< typename T >
  269.     inline void Swap(T& first, T& second)
  270.     {
  271.         T swapTemp = first;
  272.         first = second;
  273.         second = swapTemp;
  274.     };
  275.  
  276.  
  277.     template<typename T>
  278.     const int CounterBigO(int N)
  279.     {
  280.         return N + (1 << ((sizeof(T) < sizeof(int)) ? (sizeof(T) * CHAR_BITS) : (sizeof(int) * CHAR_BITS - 1)));
  281.     }
  282.  
  283.     template<typename T>
  284.     constexpr int QuickBigO(int N)
  285.     {
  286.         return N * Log2(N);
  287.     }
  288.  
  289.     template<typename T>
  290.     constexpr int RadixBigO_8(int N)
  291.     {
  292.         return sizeof(T) * (2 * N + 2 * (1 << 8));
  293.     }
  294.  
  295.     template<typename T>
  296.     constexpr int RadixBigO_16(int N)
  297.     {
  298.         return (sizeof(T) >> 1) * (2 * N + 2 * (1 << 16));
  299.     }
  300.  
  301.     template<typename T>
  302.     constexpr int RadixBigO(int N)
  303.     {
  304.         if (sizeof(T) < sizeof(int))
  305.         {
  306.             return RadixBigO_8<T>(N);
  307.         }
  308.         return Min(RadixBigO_8<T>(N), RadixBigO_16<T>(N));
  309.     }
  310.  
  311.     constexpr bool IsInsertSort(int N)
  312.     {
  313.         return N < g_insertKeyValue;
  314.     }
  315.  
  316.     template<typename T>
  317.     constexpr bool IsCounterSort(int N)
  318.     {
  319.         if (std::numeric_limits<T>::is_integer && sizeof(T) <= sizeof(short))
  320.         {
  321.             return CounterBigO<T>(N) < 2* Min(QuickBigO<T>(N), RadixBigO<T>(N));
  322.         }
  323.         return false;
  324.     }
  325.  
  326.     template<typename T>
  327.     constexpr bool IsQuickSort(int N)
  328.     {
  329.         return 3 * QuickBigO<T>(N) < RadixBigO<T>(N);
  330.     }
  331.  
  332.     template<typename T>
  333.     class Sort
  334.     {
  335.     public:
  336.         void virtual operator()(T* const _first, T* const _last) = 0;
  337.     };
  338.  
  339.     template<typename T>
  340.     class InsertSort : public Sort<T>
  341.     {
  342.     public:
  343.         void operator()(T* const _first, T* const _last)
  344.         {
  345.             T* iteratorPointer = _first;
  346.  
  347.             while (++iteratorPointer < _last)
  348.             {
  349.                 T  temp = *iteratorPointer;
  350.                 T*  now = iteratorPointer;
  351.  
  352.                 while (now > _first)
  353.                 {
  354.                     if (temp > *(now - 1))
  355.                     {
  356.                         break;
  357.                     }
  358.  
  359.                     *now = *(now - 1);
  360.                     now--;
  361.                 }
  362.  
  363.                 *now = temp;
  364.             }
  365.             return;
  366.         }
  367.     };
  368.  
  369.     template<typename T>
  370.     class CounterSort : public Sort<T>
  371.     {
  372.     private:
  373.         const    unsigned int m_cacheSize;
  374.         const       long long  m_moveValue;
  375.         unsigned    long long* m_cache;
  376.     public:
  377.         CounterSort()
  378.             : m_cacheSize(1 << ((sizeof(T) < sizeof(int)) ? (sizeof(T) * CHAR_BITS) : (sizeof(short) * CHAR_BITS - 1)))
  379.             , m_moveValue(m_cacheSize >> 1)
  380.         {
  381.             m_cache = new unsigned long long[m_cacheSize];
  382.         }
  383.  
  384.         ~CounterSort()
  385.         {
  386.             SAFE_DELETE_ARRAY(m_cache);
  387.         }
  388.  
  389.         void operator()(T* const _first, T* const _last)
  390.         {
  391.             memset(m_cache, 0, m_cacheSize * sizeof(unsigned long long));
  392.  
  393.             T* iteratorPointer = _first;
  394.  
  395.             while (iteratorPointer < _last)
  396.             {
  397.                 m_cache[static_cast<long long>(*iteratorPointer) + m_moveValue]++;
  398.                 iteratorPointer++;
  399.             }
  400.  
  401.             iteratorPointer = _first;
  402.  
  403.             for (long long i = 0; i < m_cacheSize; i++)
  404.             {
  405.                 while (m_cache[i]--)
  406.                 {
  407.                     *iteratorPointer = static_cast<T>(i - m_moveValue);
  408.                     iteratorPointer++;
  409.                 }
  410.             }
  411.  
  412.             iteratorPointer = nullptr;
  413.  
  414.             return;
  415.         }
  416.     };
  417.  
  418.     template<typename T>
  419.     class QuickSort_Real : public Sort<T>
  420.     {
  421.     private:
  422.         InsertSort<T> m_insertSort;
  423.     public:
  424.         QuickSort_Real(int _size = 0){ }
  425.  
  426.         void operator()(T* const _first, T* const _last)
  427.         {
  428.             if (_last - _first < g_insertKeyValue)
  429.             {
  430.                 m_insertSort(_first, _last);
  431.                 return;
  432.             }
  433.  
  434.             Swap(*_first, *(_first + (_last - _first) / 2));
  435.  
  436.             T  temp = *_first;
  437.             T* leftIteratorPointer = _first;
  438.             T* rightIteratorPointer = _last;
  439.  
  440.             while (
  441.                 [&]() -> bool
  442.             {
  443.                 while (leftIteratorPointer < --rightIteratorPointer)
  444.                 {
  445.                     if (*rightIteratorPointer < temp)
  446.                     {
  447.                         return true;
  448.                     }
  449.                 }
  450.                 return false;
  451.             }()
  452.                 &&
  453.                 [&]() -> bool
  454.             {
  455.                 while (++leftIteratorPointer < rightIteratorPointer)
  456.                 {
  457.                     if (*leftIteratorPointer > temp)
  458.                     {
  459.                         Swap(*leftIteratorPointer, *rightIteratorPointer);
  460.  
  461.                         return true;
  462.                     }
  463.                 }
  464.                 return false;
  465.             }()
  466.                 );
  467.  
  468.             *_first = *rightIteratorPointer;
  469.             *rightIteratorPointer = temp;
  470.  
  471.             operator()(_first, rightIteratorPointer);
  472.             operator()(++leftIteratorPointer, _last);
  473.  
  474.             return;
  475.         }
  476.     };
  477.  
  478.     template<typename T>
  479.     class QuickSort_Integer : public Sort<T>
  480.     {
  481.     private:
  482.         InsertSort<T> m_insertSort;
  483.         T**           m_memoryLeftTemp;
  484.         T**           m_memoryRightTemp;
  485.         T**           m_memoryStart;
  486.         T**           m_memoryLast;
  487.         const int     m_size;
  488.     public:
  489.         QuickSort_Integer(int _size)
  490.             : m_size(_size)
  491.         {
  492.             m_memoryStart = new T*[m_size];
  493.             m_memoryLast = &m_memoryStart[m_size - 1];
  494.             m_memoryLeftTemp = m_memoryStart;
  495.             m_memoryRightTemp = m_memoryLast;
  496.         }
  497.  
  498.         ~QuickSort_Integer()
  499.         {
  500.             SAFE_DELETE_ARRAY(m_memoryStart);
  501.             m_memoryLast = nullptr;
  502.             m_memoryLeftTemp = nullptr;
  503.             m_memoryRightTemp = nullptr;
  504.         }
  505.  
  506.         void operator()(T* const _first, T* const _last)
  507.         {
  508.             if (_last - _first < g_insertKeyValue)
  509.             {
  510.                 m_insertSort(_first, _last);
  511.                 return;
  512.             }
  513.  
  514.             Swap(*_first, *(_first + (_last - _first) / 2));
  515.  
  516.             T  temp = *_first;
  517.             T* leftIteratorPointer = _first;
  518.             T* rightIteratorPointer = _last;
  519.             m_memoryLeftTemp = m_memoryStart;
  520.             m_memoryRightTemp = m_memoryLast;
  521.  
  522.             while (
  523.                 [&]() -> bool
  524.             {
  525.                 while (leftIteratorPointer < --rightIteratorPointer)
  526.                 {
  527.                     if (*rightIteratorPointer < temp)
  528.                     {
  529.                         return true;
  530.                     }
  531.                     else if (*rightIteratorPointer == temp)
  532.                     {
  533.                         *m_memoryRightTemp = rightIteratorPointer;
  534.                         m_memoryRightTemp--;
  535.                     }
  536.                 }
  537.                 return false;
  538.             }()
  539.                 &&
  540.                 [&]() -> bool
  541.             {
  542.                 while (++leftIteratorPointer < rightIteratorPointer)
  543.                 {
  544.                     if (*leftIteratorPointer > temp)
  545.                     {
  546.                         Swap(*leftIteratorPointer, *rightIteratorPointer);
  547.                         return true;
  548.                     }
  549.                     else if (*leftIteratorPointer == temp)
  550.                     {
  551.                         *m_memoryLeftTemp = leftIteratorPointer;
  552.                         m_memoryLeftTemp++;
  553.                     }
  554.                 }
  555.                 return false;
  556.             }()
  557.                 );
  558.  
  559.             *_first = *rightIteratorPointer;
  560.             *rightIteratorPointer = temp;
  561.  
  562.             while (--m_memoryLeftTemp >= m_memoryStart)
  563.             {
  564.                 rightIteratorPointer--;
  565.                 **m_memoryLeftTemp = *rightIteratorPointer;
  566.                 *rightIteratorPointer = temp;
  567.             }
  568.  
  569.             while (++m_memoryRightTemp <= m_memoryLast)
  570.             {
  571.                 leftIteratorPointer++;
  572.                 **m_memoryRightTemp = *leftIteratorPointer;
  573.                 *leftIteratorPointer = temp;
  574.             }
  575.  
  576.             operator()(_first, rightIteratorPointer);
  577.             operator()(++leftIteratorPointer, _last);
  578.  
  579.             return;
  580.         }
  581.     };
  582.  
  583.     template<typename T, RADIX_TYPE TYPE>
  584.     class RadixSort : public Sort<T>
  585.     {
  586.         using SHIFT_TYPE = std::conditional_t
  587.             <
  588.             TYPE == RT_8BIT,
  589.             unsigned      char,
  590.             unsigned     short
  591.             > ;
  592.  
  593.         union UNION_TYPE
  594.         {
  595.             T          OriginType;
  596.             SHIFT_TYPE shiftArray[sizeof(T) / sizeof(SHIFT_TYPE)];
  597.         };
  598.  
  599.         const int        m_size;
  600.  
  601.         const long long  m_shiftNum;
  602.         const SHIFT_TYPE m_cacheMSB;
  603.         const SHIFT_TYPE m_cacheMSBInvert;
  604.  
  605.         unsigned int m_cacheSize;
  606.         unsigned int m_cacheHalfSize;
  607.         long long*   m_cachePlus;
  608.         long long*   m_cachePlusHalfPoint;
  609.         long long*   m_cacheMinus;
  610.         UNION_TYPE*  m_memory;
  611.  
  612.         void RadixNormal(UNION_TYPE* const _srcFirst, UNION_TYPE* const _dstFirst, const long long _index)
  613.         {
  614.             memset(m_cachePlus, 0, m_cacheSize * sizeof(long long));
  615.  
  616.             UNION_TYPE* srcIterator = _srcFirst;
  617.             const UNION_TYPE* srcLast = _srcFirst + m_size;
  618.  
  619.             while (srcIterator < srcLast)
  620.             {
  621.                 m_cachePlus[srcIterator->shiftArray[_index]]++;
  622.                 srcIterator++;
  623.             }
  624.  
  625.             long long* cacheIterator = m_cachePlus + m_cacheSize - 1;
  626.  
  627.             *cacheIterator = m_size - *cacheIterator;
  628.  
  629.             while (m_cachePlus <= --cacheIterator)
  630.             {
  631.                 *cacheIterator = *(cacheIterator + 1) - *cacheIterator;
  632.             }
  633.  
  634.             srcIterator = _srcFirst;
  635.  
  636.             while (srcIterator < srcLast)
  637.             {
  638.                 (_dstFirst + m_cachePlus[srcIterator->shiftArray[_index]])->OriginType = srcIterator->OriginType;
  639.                 m_cachePlus[srcIterator->shiftArray[_index]]++;
  640.                 srcIterator++;
  641.             }
  642.         }
  643.  
  644.         void RadixFinal_Real(UNION_TYPE* const _srcFirst, UNION_TYPE* const _dstFirst, const long long _index)
  645.         {
  646.             memset(m_cachePlus, 0, m_cacheHalfSize * sizeof(long long));
  647.             memset(m_cacheMinus, 0, m_cacheHalfSize * sizeof(long long));
  648.  
  649.             UNION_TYPE*   srcIterator = _srcFirst;
  650.             const UNION_TYPE* srcLast = _srcFirst + m_size;
  651.  
  652.             while (srcIterator < srcLast)
  653.             {
  654.                 SHIFT_TYPE tempMSB = srcIterator->shiftArray[_index] & m_cacheMSB;
  655.                 SHIFT_TYPE tempRest;
  656.  
  657.                 if (tempMSB)
  658.                 {
  659.                     tempRest = (srcIterator->shiftArray[_index] + 1) & m_cacheMSBInvert;
  660.                     m_cacheMinus[tempRest]++;
  661.                 }
  662.                 else
  663.                 {
  664.                     tempRest = srcIterator->shiftArray[_index] & m_cacheMSBInvert;
  665.                     m_cachePlus[tempRest]++;
  666.                 }
  667.                 srcIterator++;
  668.             }
  669.  
  670.             long long* cachePlusIterator = m_cachePlus + m_cacheHalfSize - 1;
  671.             long long* cacheMinusIterator = m_cacheMinus + m_cacheHalfSize - 1;
  672.  
  673.             *cachePlusIterator = *cachePlusIterator - 1;
  674.             *cacheMinusIterator = *cacheMinusIterator - 1;
  675.  
  676.             cachePlusIterator--;
  677.             cacheMinusIterator--;
  678.  
  679.             while (cachePlusIterator >= m_cachePlus)
  680.             {
  681.                 *cachePlusIterator = *(cachePlusIterator + 1) + *cachePlusIterator;
  682.                 *cacheMinusIterator = *(cacheMinusIterator + 1) + *cacheMinusIterator;
  683.  
  684.                 cachePlusIterator--;
  685.                 cacheMinusIterator--;
  686.             }
  687.  
  688.             srcIterator = _srcFirst;
  689.  
  690.             UNION_TYPE* const dstLast = _dstFirst + m_size - 1;
  691.  
  692.             while (srcIterator < srcLast)
  693.             {
  694.                 SHIFT_TYPE tempMSB = srcIterator->shiftArray[_index] & m_cacheMSB;
  695.                 SHIFT_TYPE tempRest;
  696.  
  697.                 if (tempMSB)
  698.                 {
  699.                     tempRest = (srcIterator->shiftArray[_index] + 1) & m_cacheMSBInvert;
  700.                     (_dstFirst + m_cacheMinus[tempRest])->OriginType = srcIterator->OriginType;
  701.                     m_cacheMinus[tempRest]--;
  702.                 }
  703.                 else
  704.                 {
  705.                     tempRest = srcIterator->shiftArray[_index] & m_cacheMSBInvert;
  706.                     (dstLast - m_cachePlus[tempRest])->OriginType = srcIterator->OriginType;
  707.                     m_cachePlus[tempRest]--;
  708.                 }
  709.                 srcIterator++;
  710.             }
  711.         }
  712.  
  713.         void RadixFinal_Integer(UNION_TYPE* const _srcFirst, UNION_TYPE* const _dstFirst, const long long _index)
  714.         {
  715.             memset(m_cachePlus, 0, m_cacheHalfSize * sizeof(long long));
  716.             memset(m_cacheMinus, 0, m_cacheHalfSize * sizeof(long long));
  717.  
  718.             UNION_TYPE*   srcIterator = _srcFirst         ;
  719.             const UNION_TYPE* srcLast = _srcFirst + m_size;
  720.  
  721.             while (srcIterator < srcLast)
  722.             {
  723.                 SHIFT_TYPE tempMSB = srcIterator->shiftArray[_index] & m_cacheMSB;
  724.                 SHIFT_TYPE tempRest;
  725.  
  726.                 if (tempMSB)
  727.                 {
  728.                     tempRest = srcIterator->shiftArray[_index] & m_cacheMSBInvert;
  729.                     m_cacheMinus[tempRest]++;
  730.                 }
  731.                 else
  732.                 {
  733.                     tempRest = srcIterator->shiftArray[_index] & m_cacheMSBInvert;
  734.                     m_cachePlus[tempRest]++;
  735.                 }
  736.                 srcIterator++;
  737.             }
  738.  
  739.             long long* cachePlusIterator = m_cachePlus + m_cacheHalfSize - 1;
  740.             long long* cacheMinusIterator = m_cacheMinus;
  741.  
  742.             long long  cacheMinusTemp = *cacheMinusIterator;
  743.             long long  cacheMinusSum = 0;
  744.  
  745.             *cachePlusIterator = *cachePlusIterator - 1;
  746.             *cacheMinusIterator = 0;
  747.  
  748.             cachePlusIterator--;
  749.             cacheMinusIterator++;
  750.  
  751.             while (cachePlusIterator >= m_cachePlus)
  752.             {
  753.                 cacheMinusSum += cacheMinusTemp;
  754.                 cacheMinusTemp = *cacheMinusIterator;
  755.                 *cachePlusIterator = *(cachePlusIterator + 1) + *cachePlusIterator;
  756.                 *cacheMinusIterator = cacheMinusSum;
  757.  
  758.                 cachePlusIterator--;
  759.                 cacheMinusIterator++;
  760.             }
  761.  
  762.             srcIterator = _srcFirst;
  763.  
  764.             UNION_TYPE* const dstLast = _dstFirst + m_size - 1;
  765.  
  766.             while (srcIterator < srcLast)
  767.             {
  768.                 SHIFT_TYPE tempMSB = srcIterator->shiftArray[_index] & m_cacheMSB;
  769.                 SHIFT_TYPE tempRest;
  770.  
  771.                 if (tempMSB)
  772.                 {
  773.                     tempRest = srcIterator->shiftArray[_index] & m_cacheMSBInvert;
  774.                     (_dstFirst + m_cacheMinus[tempRest])->OriginType = srcIterator->OriginType;
  775.                     m_cacheMinus[tempRest]++;
  776.                 }
  777.                 else
  778.                 {
  779.                     tempRest = srcIterator->shiftArray[_index] & m_cacheMSBInvert;
  780.                     (dstLast - m_cachePlus[tempRest])->OriginType = srcIterator->OriginType;
  781.                     m_cachePlus[tempRest]--;
  782.                 }
  783.                 srcIterator++;
  784.             }
  785.         }
  786.  
  787.         const unsigned int GetCacheSize()
  788.         {
  789.             if (sizeof(T) <= sizeof(short))
  790.             {
  791.                 return (1 << sizeof(char) * CHAR_BITS);
  792.             }
  793.             return (RadixBigO_8<T>(m_size) < RadixBigO_16<T>(m_size)) ? (1 << sizeof(char) * CHAR_BITS) : (1 << sizeof(short) * CHAR_BITS);
  794.         }
  795.     public:
  796.         RadixSort(int _size)
  797.             : m_shiftNum(sizeof(T) / sizeof(SHIFT_TYPE) - 1)
  798.             , m_cacheMSB(1 << (sizeof(SHIFT_TYPE) * CHAR_BITS - 1))
  799.             , m_cacheMSBInvert(m_cacheMSB ^ (static_cast<SHIFT_TYPE>(0) - 1))
  800.             , m_size(_size)
  801.         {
  802.             m_cacheSize = GetCacheSize();
  803.             m_cacheHalfSize = m_cacheSize >> 1;
  804.  
  805.             m_cachePlus  = new  long long[m_cacheSize];
  806.             m_cacheMinus = new  long long[m_cacheHalfSize];
  807.             m_memory     = new UNION_TYPE[m_size];
  808.  
  809.             m_cachePlusHalfPoint = m_cachePlus + m_cacheHalfSize;
  810.         }
  811.  
  812.         ~RadixSort()
  813.         {
  814.             SAFE_DELETE_ARRAY(m_cachePlus);
  815.             SAFE_DELETE_ARRAY(m_cacheMinus);
  816.             SAFE_DELETE_ARRAY(m_memory);
  817.  
  818.             m_cachePlusHalfPoint = nullptr;
  819.         }
  820.  
  821.         void operator()(T* const _first, T* const _last)
  822.         {
  823.             UNION_TYPE* src = reinterpret_cast<UNION_TYPE*>(_first);
  824.             UNION_TYPE* dst = m_memory;
  825.  
  826.             long long index = 0LL;
  827.  
  828.             while (index < m_shiftNum)
  829.             {
  830.                 RadixNormal(src, dst, index);
  831.                 Swap(src, dst);
  832.                 index++;
  833.             }
  834.  
  835.             if (std::numeric_limits<T>::is_integer)
  836.             {
  837.                 RadixFinal_Integer(src, dst, index);
  838.             }
  839.             else
  840.             {
  841.                 RadixFinal_Real(src, dst, index);
  842.             }
  843.             return;
  844.         }
  845.     };
  846.  
  847.  
  848.     template<bool _flag, typename T>
  849.     struct QuickSort
  850.     {
  851.         typedef QuickSort_Real  <T> type;
  852.     };
  853.  
  854.     template<typename T>
  855.     struct QuickSort<true, T>
  856.     {
  857.         typedef QuickSort_Integer<T> type;
  858.     };
  859.  
  860.     template<typename T>
  861.     using QuickSort_t = typename QuickSort<std::numeric_limits<T>::is_integer, T>::type;
  862.  
  863.     template<typename T>
  864.     class SortController
  865.     {
  866.     private:
  867.         SortController() 
  868.         {
  869.             std::atexit(Destroy);
  870.         };
  871.         ~SortController() {};
  872.  
  873.         static Sort<T>* m_instance;
  874.  
  875.     public:
  876.         static void Destroy()
  877.         {
  878.             delete m_instance;
  879.             m_instance = nullptr;
  880.         }
  881.  
  882.         static Sort<T>* GetInstance(const int _size)
  883.         {
  884.             if (m_instance == nullptr)
  885.             {
  886.                 if (IsInsertSort(_size))
  887.                 {
  888.                     m_instance = new InsertSort<T>();
  889.                 }
  890.                 else if (IsCounterSort<T>(_size))
  891.                 {
  892.                     m_instance = new CounterSort<T>();
  893.                 }
  894.                 else if (IsQuickSort<T>(_size))
  895.                 {
  896.                     m_instance = new QuickSort_t<T>(_size);
  897.                 }
  898.                 else
  899.                 {
  900.                     if (RadixBigO_8<T>(_size) < RadixBigO_16<T>(_size) || sizeof(T) <= sizeof(short))
  901.                     {
  902.                         m_instance = new RadixSort  <T, RT_8BIT>(_size);
  903.                     }
  904.                     else
  905.                     {
  906.                         m_instance = new RadixSort  <T, RT_16BIT>(_size);
  907.                     }
  908.                 }
  909.             }
  910.             return m_instance;
  911.         }
  912.     };
  913.  
  914.     template <typename T>
  915.     Sort<T>* SortController<T>::m_instance = nullptr;
  916.  
  917.     template<typename T = SOURCE>
  918.     void run(void* dst)
  919.     {
  920.         T* arr = static_cast<T*>(dst);
  921.  
  922.         Sort<T>& m_sort = *(SortController<T>::GetInstance(SIZE));
  923.  
  924.         m_sort(arr, arr + SIZE);
  925.  
  926.         return;
  927.     }
  928.  
  929. };
  930.  
  931. int main(int argc, char* argv[])
  932. {
  933.     std::random_device randomDevice;
  934.     std::mt19937 rng(randomDevice());
  935. //    std::normal_distribution< DISTRIBUTION_SOURCE > get(5, 2);
  936.     std::uniform_int_distribution< int > get;
  937.  
  938.     for (auto& value : src)
  939.     {
  940.         value = static_cast<SOURCE>(get(rng));
  941.     }
  942.  
  943.     BENCH bench("sort", 100, Prepare, Compare);
  944.     bench.Solution(BOSS::run, dst0, sizeof dst0); // 정답 참고용 함수 등록.
  945.     bench.Add(FUN(BOSS::run), dst1);
  946.     bench.Add(FUN(PENZER::run), dst2);
  947.  
  948.     bench.run();
  949.  
  950.     unsigned short* temp = reinterpret_cast<unsigned short*>(dst2);
  951.  
  952.     for (int i = 0; i < 10; i++)
  953.     {
  954.     printf("%4X ", *(temp + i));
  955.  
  956.     }
  957.     getchar();
  958.  
  959.     return 0;
  960. }
Success #stdin #stdout 0s 15272KB
comments (?)
stdin 
Standard input is empty
stdout 
Penzer's debug log - DataType: A2048_s

   < 64 bits 100 trial >    sort
   ----------------+---------------------------------+-----------------------
   |    CHECKER    |          function name          |    minimum clocks    |
   ----------------+---------------------------------+-----------------------
   [        PASSED ]                        BOSS::run          181210 clocks
   [        PASSED ]                      PENZER::run           26734 clocks
   --------------------------------------------------------------------------
   PENZER is faster than BOSS  ( 6.78 times faster )

8005 802A 806A 806C 8081 808C 8096 80AB 80B2 80B5
https://ideone.com/z0Z44e
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!