fork(10) download
copy 
  1. // test code for http://stackoverflow.com/questions/24542936/
  2.  
  3. #include <vector>
  4. #include <set>
  5. #include <algorithm>
  6. #include <chrono>
  7. #include <iostream>
  8. #include <cstdlib>
  9. #include <ctime>
  10.  
  11. #include <ext/pb_ds/assoc_container.hpp>
  12. #include <ext/pb_ds/tree_policy.hpp>
  13.  
  14. const int N = 20000;
  15.  
  16. // reused from https://i...content-available-to-author-only...e.com/MN7DYK
  17. struct timer
  18. {
  19. 	typedef std::chrono::high_resolution_clock clock;
  20. 	clock::time_point start_;
  21.  
  22. 	timer() : start_(clock::now()) {}
  23. 	~timer()
  24. 	{
  25. 		std::cout
  26. 		<< ((double)std::chrono::duration_cast<std::chrono::microseconds>(clock::now() - start_).count() / 1000.)
  27. 		<< "ms" << std::endl;
  28. 	}
  29. };
  30.  
  31. void test_vector() {
  32. 	timer t;
  33. 	std::vector<int> c;
  34.  
  35. 	// insert elements randomly while maintaining order
  36. 	for(int i = 0; i < N; ++i) {
  37. 		int r = rand();
  38.  
  39. 		// linear search for insert position
  40. 		auto position = c.end();
  41. 		for(auto it = c.begin(); it != c.end(); ++it) {
  42. 			if(*it >= r) {
  43. 				position = it;
  44. 				break;
  45. 			}
  46. 		}
  47. 		c.insert(position, r);
  48. 	}
  49.  
  50. 	// remove randomly while maintaining order
  51. 	for(auto i = c.size() - 1; i > 0; --i) {
  52. 		auto it = c.begin();
  53. 		std::advance(it, rand() % i);
  54. 		c.erase(it);
  55. 	}
  56. }
  57.  
  58. void test_bsvector() {
  59. 	timer t;
  60. 	std::vector<int> c;
  61.  
  62. 	// insert elements randomly while maintaining order
  63. 	for(int i = 0; i < N; ++i) {
  64. 		int r = rand();
  65.  
  66. 		// binary search
  67. 		c.insert(std::lower_bound(c.begin(), c.end(), r), r);
  68. 	}
  69.  
  70. 	// remove randomly while maintaining order
  71. 	for(auto i = c.size() - 1; i > 0; --i) {
  72. 		auto it = c.begin();
  73. 		std::advance(it, rand() % i);
  74. 		c.erase(it);
  75. 	}
  76. }
  77.  
  78. void test_set() {
  79. 	timer t;
  80. 	std::set<int> c;
  81.  
  82. 	// insert elements randomly while maintaining order
  83. 	for(int i = 0; i < N; ++i)
  84. 		c.insert(rand()); // logarithmic search
  85.  
  86. 	// remove randomly while maintaining order
  87. 	// if you have a faster algorithm, please share
  88. 	for(auto i = c.size() - 1; i > 0; --i) {
  89. 		auto it = c.begin();
  90. 		std::advance(it, rand() % i);
  91. 		c.erase(it);
  92. 	}
  93. }
  94.  
  95. using namespace __gnu_pbds;
  96.  
  97. typedef
  98. 	tree<
  99. 	int,
  100. 	int,
  101. 	std::less<int>,
  102. 	rb_tree_tag,
  103. 	tree_order_statistics_node_update>
  104. map_t;
  105.  
  106. void test_ost() {
  107. 	timer t;
  108. 	map_t c;
  109.  
  110. 	// insert elements randomly while maintaining order
  111. 	for(int i = 0; i < N; ++i) {
  112. 		int r = rand();
  113. 		c.insert(std::make_pair(r, r)); // logarithmic search
  114. 	}
  115.  
  116. 	// remove randomly while maintaining order
  117. 	for(auto i = c.size() - 1; i > 0; --i) {
  118. 		c.erase(c.find_by_order(rand() % i));
  119. 	}
  120. }
  121.  
  122. int main() {
  123. 	unsigned int seed = std::time(nullptr);
  124. 	std::srand(seed);
  125. 	std::cout << "order statistics tree: ";
  126. 	test_ost();
  127. 	std::srand(seed);
  128. 	std::cout << "vector binary search: ";
  129. 	test_bsvector();
  130. 	std::srand(seed);
  131. 	std::cout << "vector linear search: ";
  132. 	test_vector();
  133. 	std::srand(seed);
  134. 	std::cout << "set: ";
  135. 	test_set();
  136. }
  137.  
Success #stdin #stdout 2.4s 3836KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
order statistics tree: 15.958ms
vector binary search: 99.661ms
vector linear search: 282.032ms
set: 2004.04ms
https://ideone.com/DoqL4H
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!