fork(3) download
copy 
  1. #pragma GCC optimize("Ofast")
  2. #include <bits/stdc++.h>
  3.  
  4. uint32_t xorshift32(uint32_t x) {
  5. 	x ^= x << 13;
  6. 	x ^= x >> 17;
  7. 	return x ^= x << 5;
  8. }
  9.  
  10. using namespace std;
  11.  
  12. const int n = (1<<20);
  13. const int block_size = 16;
  14. alignas(64) int a[n], b[n * 2];
  15.  
  16. int eytzinger(int i = 0, int k = 1) {
  17.     if (k <= n) {
  18.         i = eytzinger(i, 2 * k);
  19.         b[k] = a[i++];
  20.         i = eytzinger(i, 2 * k + 1);
  21.     }
  22.     return i;
  23. }
  24.  
  25. int search(int x) {
  26.     int k = 1;
  27.     while (k <= n) {
  28.         __builtin_prefetch(b + k * block_size);
  29.         k = 2 * k + (b[k] < x);
  30.     }
  31.     return k - n + 1;
  32. }
  33.  
  34. int main() {
  35. 	std::cout << std::fixed << std::setprecision(3);
  36. 	for (int i = 0; i < n; i++) {
  37. 		a[i] = i;
  38. 	}
  39. 	eytzinger();
  40. 	{
  41. 		double tin = (double)clock();
  42. 		uint32_t x = 1, check = 0;
  43. 		for (int i = 0; i < (1 << 20); i++) {
  44. 			x = xorshift32(x);
  45. 			check ^= search(x % n);
  46. 		}
  47. 		double tout = (double)clock();
  48. 		std::cout << "eytzinger = " << (tout - tin) / CLOCKS_PER_SEC << "s, check = " << check << std::endl;
  49. 	}
  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 ^= int(std::lower_bound(a, a + n, x % n) - a);
  56. 		}
  57. 		double tout = (double)clock();
  58. 		std::cout << "lower_bound = " << (tout - tin) / CLOCKS_PER_SEC << "s, check = " << check << std::endl;
  59. 	}
  60. 	return 0;
  61. }
Success #stdin #stdout 0.31s 11952KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
eytzinger = 0.112s, check = 377557
lower_bound = 0.189s, check = 377557
https://ideone.com/IeWTJ1
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!