fork download
copy 
  1. // By Aliaksei Sanko
  2. // http://l...content-available-to-author-only...d.in/kVJXfm
  3. // http://a...content-available-to-author-only...l.com/
  4.  
  5. #include <algorithm>
  6. #include <iostream>
  7.  
  8. #include <time.h>
  9.  
  10. using std::cout;
  11. using std::cerr;
  12. using std::endl;
  13.  
  14. #define ITER(stage)     \
  15. if (stage <= curPlace)  \
  16. {                       \
  17.     enum { OFFSET = (1 << stage) / 2 }; \
  18.     typedef I Array[OFFSET]; \
  19.     first = ((Array*) first)[*(first + (OFFSET - 1)) < val]; \
  20. }
  21.  
  22. template <int curPlace, typename I, typename V>
  23. inline
  24. I* fast_lower_bound(I* first, const V& val)
  25. {
  26.     ITER(28)
  27.     ITER(27)
  28.     ITER(26)
  29.     ITER(25)
  30.     ITER(24)
  31.     ITER(23)
  32.     ITER(22)
  33.     ITER(21)
  34.     ITER(20)
  35.     ITER(19)
  36.     ITER(18)
  37.     ITER(17)
  38.     ITER(16)
  39.     ITER(15)
  40.     ITER(14)
  41.     ITER(13)
  42.     ITER(12)
  43.     ITER(11)
  44.     ITER(10)
  45.     ITER(9)
  46.     ITER(8)
  47.     ITER(7)
  48.     ITER(6)
  49.     ITER(5)
  50.     ITER(4)
  51.     ITER(3)
  52.     ITER(2)
  53.     ITER(1)
  54.  
  55.     return first;
  56. }
  57.  
  58.  
  59. #define HANDLE_GROUPS_3(a, b, c) \
  60.     HANDLE_GROUPS_4(a, b, c, 0) \
  61.     HANDLE_GROUPS_4(a, b, c, 1) \
  62.     HANDLE_GROUPS_4(a, b, c, 2) \
  63.     HANDLE_GROUPS_4(a, b, c, 3)
  64.  
  65. #define HANDLE_GROUPS_2(a, b) \
  66.     HANDLE_GROUPS_3(a, b, 0) \
  67.     HANDLE_GROUPS_3(a, b, 1) \
  68.     HANDLE_GROUPS_3(a, b, 2) \
  69.     HANDLE_GROUPS_3(a, b, 3)
  70.  
  71.  
  72. #define HANDLE_GROUPS_1(a) \
  73.     HANDLE_GROUPS_2(a, 0) \
  74.     HANDLE_GROUPS_2(a, 1) \
  75.     HANDLE_GROUPS_2(a, 2) \
  76.     HANDLE_GROUPS_2(a, 3)
  77.  
  78.  
  79. #define HANDLE_GROUPS_4(a, b, c, d) \
  80. case (a * 64 + b * 16 + c * 4 + d): \
  81. { \
  82.     enum { flags = (a * 64 + b * 16 + c * 4 + d) }; \
  83.     HANDLE_FLAG(6); \
  84.     HANDLE_FLAG(5); \
  85.     HANDLE_FLAG(4); \
  86.     HANDLE_FLAG(3); \
  87.     HANDLE_FLAG(2); \
  88.     HANDLE_FLAG(1); \
  89.     HANDLE_FLAG(0); \
  90.     break; \
  91. }
  92.  
  93. #define HANDLE_FLAG(flag) \
  94. { \
  95.     enum { curPlace = flag + SEGMENT * 7 }; \
  96.     if (*(first + ((1 << curPlace) - 1)) < val) \
  97.         first += (1 << curPlace); \
  98.     else \
  99.         return fast_lower_bound<curPlace>(first, val); \
  100.     if (flags & (1 << flag)) \
  101.     { \
  102.         if (*(first + ((1 << curPlace) - 1)) < val) \
  103.             first += (1 << curPlace); \
  104.         else \
  105.             return fast_lower_bound<curPlace>(first, val); \
  106.     } \
  107. }
  108.  
  109.  
  110. template <typename I, int SEGMENT>
  111. struct bound_continue_helper
  112. {
  113.     template<typename V>
  114.     static I lower_bound_ex(I first, unsigned int distance, const V& val)
  115.     {
  116.         switch ((distance >> (SEGMENT * 7)) & 127)
  117.         {
  118.             HANDLE_GROUPS_1(0)
  119.             HANDLE_GROUPS_1(1)
  120.         }
  121.  
  122.         return bound_continue_helper<I, SEGMENT - 1>::lower_bound_ex(first, distance, val);
  123.     }
  124. };
  125.  
  126. template <typename I>
  127. struct bound_continue_helper<I, -1>
  128. {
  129.     template<typename V>
  130.     static I lower_bound_ex(I first, unsigned int, const V&)
  131.     {
  132.         return first;
  133.     }
  134. };
  135.  
  136. #undef HANDLE_GROUPS_4
  137. #define HANDLE_GROUPS_4(a, b, c, d) \
  138. case (a * 64 + b * 16 + c * 4 + d): \
  139. { \
  140.     enum { flags = (a * 64 + b * 16 + c * 4 + d) }; \
  141.     if (0 == flags) \
  142.         return bound_entry_helper<I, SEGMENT-1>::lower_bound_ex(first, distance, val); \
  143.     HANDLE_FLAG(6); \
  144.     HANDLE_FLAG(5); \
  145.     HANDLE_FLAG(4); \
  146.     HANDLE_FLAG(3); \
  147.     HANDLE_FLAG(2); \
  148.     HANDLE_FLAG(1); \
  149.     HANDLE_FLAG(0); \
  150.     break; \
  151. }
  152.  
  153. #undef HANDLE_FLAG
  154. #define HANDLE_FLAG(flag) \
  155. if (flags >= (1 << (flag+1))) \
  156. { \
  157.     enum { curPlace = flag + SEGMENT * 7 }; \
  158.     if (*(first + ((1 << curPlace) - 1)) < val) \
  159.         first += (1 << curPlace); \
  160.     else \
  161.         return fast_lower_bound<curPlace>(first, val); \
  162.     if (flags & (1 << flag)) \
  163.     { \
  164.         if (*(first + ((1 << curPlace) - 1)) < val) \
  165.             first += (1 << curPlace); \
  166.         else \
  167.             return fast_lower_bound<curPlace>(first, val); \
  168.     } \
  169. }
  170.  
  171. template <typename I, int SEGMENT>
  172. struct bound_entry_helper
  173. {
  174.     template<typename V>
  175.     static I lower_bound_ex(I first, unsigned int distance, const V& val)
  176.     {
  177.         switch ((distance >> (SEGMENT * 7)) & 127)
  178.         {
  179.             HANDLE_GROUPS_1(0)
  180.             HANDLE_GROUPS_1(1)
  181.         }
  182.  
  183.         return bound_continue_helper<I, SEGMENT - 1>::lower_bound_ex(first, distance, val);
  184.     }
  185. };
  186.  
  187. template <typename I>
  188. struct bound_entry_helper<I, -1>
  189. {
  190.     template<typename V>
  191.     static I lower_bound_ex(I first, unsigned int, const V&)
  192.     {
  193.         return first;
  194.     }
  195. };
  196.  
  197.  
  198. template<typename I, typename V>
  199. inline I lower_bound_ex(I first, I last,
  200.                         const V& val)
  201. {
  202.     unsigned int distance = (unsigned int) (last - first);
  203.     unsigned int flags = distance + 1;
  204.  
  205.     return (flags >= 0x00004000)
  206.         ? bound_entry_helper<I, 3>::lower_bound_ex(first, flags, val)
  207.         : bound_entry_helper<I, 1>::lower_bound_ex(first, flags, val);
  208. }
  209.  
  210.  
  211. unsigned int HashKey(int key)
  212. {
  213.     return (key * 2654435761UL) >> 11;
  214. }
  215.  
  216.  
  217. void DoTest(int size, int iterations)
  218. {
  219.     cout << "size: " << size << "; iterations: " << iterations << endl;
  220.  
  221.     int* arr = new int[size + 1];
  222.  
  223.     for (int i = 0; i <= size; ++i)
  224.         arr[i] = i;
  225.  
  226.     clock_t start = clock();
  227.  
  228.     for (int k = 0; k < iterations; ++k)
  229.         for (int i = 0; i < size; ++i)
  230.         {
  231.             int j = (HashKey(i) % size);
  232.             int* p = lower_bound_ex(arr, arr + size - 1, j);
  233.             if (j != *p)
  234.             {
  235.                 cerr << "Erroneous lower_bound_ex test result: " << *p 
  236.                     << " instead of " << j << endl;
  237.                 exit(1);
  238.             }
  239.         }
  240.  
  241.     cout << "  lower_bound_ex time: " <<
  242.         (double)(clock() - start) / CLOCKS_PER_SEC  <<
  243.         " seconds" << endl;
  244.  
  245.     start = clock();
  246.  
  247.     for (int k = 0; k < iterations; ++k)
  248.         for (int i = 0; i < size; ++i)
  249.         {
  250.             int j = (HashKey(i) % size);
  251.             int* p = std::lower_bound(arr, arr + size - 1, j);
  252.             if (j != *p)
  253.             {
  254.                 cerr << "Erroneous std::lower_bound test result: " << *p 
  255.                     << " instead of " << j << endl;
  256.                 exit(1);
  257.             }
  258.         }
  259.  
  260.     cout << "  std::lower_bound time: " <<
  261.         (double)(clock() - start) / CLOCKS_PER_SEC  <<
  262.         " seconds" << endl;
  263.  
  264.     delete[] arr;
  265. }
  266.  
  267.  
  268. int main(int argc, char* argv[])
  269. {
  270.    DoTest(128 * 1024, 50);
  271.    DoTest(95369, 50);
  272.  
  273.    return 0;
  274. }
  275.  
Success #stdin #stdout 3.94s 3676KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
size: 131072; iterations: 50
  lower_bound_ex time: 1.08 seconds
  std::lower_bound time: 1.42 seconds
size: 95369; iterations: 50
  lower_bound_ex time: 0.65 seconds
  std::lower_bound time: 0.79 seconds
https://ideone.com/cxV1Dy
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

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!