fork download
copy 
  1. #pragma GCC optimize("Ofast")
  2. #include <bits/stdc++.h>
  3.  
  4. template<int n, typename T>
  5. int lowerBound(const T* __restrict arr, const T val) {
  6.     if (n == 1) { return val > arr[0]; } 
  7.     else {
  8.         constexpr int mid = n / 2;
  9.         if (val > arr[mid]) { return mid+lowerBound<n-mid, T>(arr+mid, val); }
  10.         else { return lowerBound<mid, T>(arr,val); }
  11.     }
  12. };
  13.  
  14. uint32_t xorshift32(uint32_t x) {
  15. 	x ^= x << 13;
  16. 	x ^= x >> 17;
  17. 	return x ^= x << 5;
  18. }
  19.  
  20. using namespace std;
  21.  
  22. const int n = (1<<20);
  23. const int block_size = 16;
  24. alignas(64) int a[n], b[n * 2];
  25.  
  26. int eytzinger(int i = 0, int k = 1) {
  27.     if (k <= n) {
  28.         i = eytzinger(i, 2 * k);
  29.         b[k] = a[i++];
  30.         i = eytzinger(i, 2 * k + 1);
  31.     }
  32.     return i;
  33. }
  34.  
  35. int search(int x) {
  36.     int k = 1;
  37.     while (k <= n) {
  38.         __builtin_prefetch(b + k * block_size);
  39.         k = 2 * k + (b[k] < x);
  40.     }
  41.     return k - n + 1;
  42. }
  43.  
  44. int main() {
  45. 	std::cout << std::fixed << std::setprecision(3);
  46. 	for (int i = 0; i < n; i++) {
  47. 		a[i] = i;
  48. 	}
  49. 	eytzinger();
  50. 	{
  51. 		double tin = (double)clock();
  52. 		uint32_t x = 1, check = 0;
  53. 		for (int i = 0; i < (1 << 20); i++) {
  54. 			x = xorshift32(x);
  55. 			check ^= search(x % n);
  56. 		}
  57. 		double tout = (double)clock();
  58. 		std::cout << "eytzinger = " << (tout - tin) / CLOCKS_PER_SEC << "s, check = " << check << std::endl;
  59. 	}
  60. 	{
  61. 		double tin = (double)clock();
  62. 		uint32_t x = 1, check = 0;
  63. 		for (int i = 0; i < (1 << 20); i++) {
  64. 			x = xorshift32(x);
  65. 			check ^= int(std::lower_bound(a, a + n, x % n) - a);
  66. 		}
  67. 		double tout = (double)clock();
  68. 		std::cout << "lower_bound = " << (tout - tin) / CLOCKS_PER_SEC << "s, check = " << check << std::endl;
  69. 	}
  70. 	{
  71. 		double tin = (double)clock();
  72. 		uint32_t x = 1, check = 0;
  73. 		for (int i = 0; i < (1 << 20); i++) {
  74. 			x = xorshift32(x);
  75. 			check ^= lowerBound<n>(a, int(x % n));
  76. 		}
  77. 		double tout = (double)clock();
  78. 		std::cout << "template = " << (tout - tin) / CLOCKS_PER_SEC << "s, check = " << check << std::endl;
  79. 	}
  80. 	return 0;
  81. }
Success #stdin #stdout 0.55s 11772KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
eytzinger = 0.157s, check = 377557
lower_bound = 0.242s, check = 377557
template = 0.138s, check = 377557
https://ideone.com/8dg28a
language:
C++14 (gcc 8.3)
created:
4 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!