fork(2) 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+1];
  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.     k >>= __builtin_ffs(~k);
  32.     return k;
  33. }
  34.  
  35. int main() {
  36. 	std::cout << std::fixed << std::setprecision(3);
  37. 	for (int i = 0; i < n; i++) {
  38. 		a[i] = i;
  39. 	}
  40. 	eytzinger();
  41. 	{
  42. 		double tin = (double)clock();
  43. 		int x = 1, check = 0;
  44. 		for (int i = 0; i < (1 << 20); i++) {
  45. 			x = xorshift32(x);
  46. 			check ^= search(x);
  47. 		}
  48. 		double tout = (double)clock();
  49. 		std::cout << "eytzinger = " << (tout - tin) / CLOCKS_PER_SEC << "s, check = " << check << std::endl;
  50. 	}
  51. 	{
  52. 		double tin = (double)clock();
  53. 		int x = 1, check = 0;
  54. 		for (int i = 0; i < (1 << 20); i++) {
  55. 			x = xorshift32(x);
  56. 			check ^= int(std::lower_bound(a,a+n,x)-a);
  57. 		}
  58. 		double tout = (double)clock();
  59. 		std::cout << "lower_bound = " << (tout - tin) / CLOCKS_PER_SEC << "s, check = " << check << std::endl;
  60. 	}
  61. 	return 0;
  62. }
Success #stdin #stdout 0.14s 11780KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
eytzinger = 0.108s, check = 1823216
lower_bound = 0.029s, check = 1852463
https://ideone.com/tSiMAC
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!