fork(1) download
copy 
  1. #pragma GCC optimize("O2")
  2. #include <bits/stdc++.h>
  3. template<int n, typename T>
  4. inline int lowerBoundImpl(const T* __restrict arr, const T val) {
  5. 	if (n == 1) { return val > arr[0]; } 
  6. 	else {
  7. 		constexpr int mid = n / 2;
  8. 		if (val > arr[mid]) { return mid+lowerBoundImpl<n-mid, T>(arr+mid, val); }
  9. 		else { return lowerBoundImpl<mid, T>(arr,val); }
  10. 	}
  11. };
  12.  
  13. template<int n, typename T>
  14. [[noinline]] int lowerBound(const T* __restrict arr, const T val) {
  15.     return lowerBoundImpl<n>(arr, val);
  16. }
  17.  
  18.  
  19. template<int n, typename T>
  20. [[noinline]] int loserBound(const T* __restrict arr, const T val) {
  21.     return int(std::lower_bound(arr,arr+n,val)-arr);
  22. }
  23.  
  24. std::vector<int> queries(1 << 9);
  25. static int arr[1 << 20];
  26. template<class T>
  27. void test(const char* s, T f) {
  28.     std::cout << s << std::endl;
  29.     int res = 0;
  30.     double tin = (double)clock(), tout;
  31.     for (int i = 0; i < (1 << 15); i++) {
  32.         for (int q : queries) {
  33.             res += f(&arr[0], q);
  34.         }
  35.     }
  36.     tout = (double)clock();
  37.     std::cout << "time = " << (tout - tin) / CLOCKS_PER_SEC << "s, sum = " << res << std::endl;
  38. }
  39.  
  40. int main() {
  41. 	for (int i = 0; i < (1 << 20); i++) { arr[i] = i; }
  42. 	std::mt19937 gen;
  43. 	std::uniform_int_distribution<int> dist(0, 1 << 20);
  44. 	for (auto &it : queries) { it = dist(gen); }
  45. 	test("Testing std::lower_bound...", loserBound<1 << 20, int>);
  46. 	test("Testing lowerBound...", lowerBound<1 << 20, int>);
  47. 	return 0;
  48. }
Success #stdin #stdout 4.73s 7880KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Testing std::lower_bound...
time = 2.94979s, sum = 1841889280
Testing lowerBound...
time = 1.77582s, sum = 1841889280
https://ideone.com/AL5ZNd
language:
C++14 (gcc 8.3)
created:
4 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!