fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <time.h>
  4. #include <assert.h>
  5. #ifdef _WIN32
  6. #define NOMINMAX
  7. #include <windows.h>
  8. #else
  9. double GetTickCount()
  10. {
  11. 	return clock() * 1000.0 / CLOCKS_PER_SEC;
  12. }
  13. #endif
  14. #include <vector>
  15. #include <set>
  16. #include <algorithm>
  17.  
  18. #if defined(_MSC_VER) && !defined(__MWERKS__) && !defined(for) && _MSC_VER <= 1200
  19. #define for if(0) {} else for
  20. #endif // _MSC_VER && !__MWERKS__ && !for && _MSC_VER <= 1200
  21. // msvc 'for' scoping hack
  22.  
  23. static int n_Rand(int n_max)
  24. {
  25. 	int n = int(rand() / (double(RAND_MAX) + 1) * (n_max + 1));
  26. 	assert(n >= 0 && n <= n_max);
  27. 	// get a random number
  28.  
  29. 	return n;
  30. }
  31.  
  32. static void Print(int i)
  33. {
  34. 	printf("%d ", i);
  35. }
  36.  
  37. struct Dec {
  38. 	void operator ()(int &r_n) const
  39. 	{
  40. 		-- r_n;
  41. 	}
  42. };
  43.  
  44. template <class CScalar>
  45. struct TNeedle {
  46. 	CScalar n;
  47.  
  48. 	TNeedle(const CScalar &r_n)
  49. 		:n(r_n)
  50. 	{}
  51. };
  52.  
  53. template <class CScalar>
  54. class CCompareWithOffset {
  55. protected:
  56. 	typename std::vector<CScalar>::iterator m_p_begin_it; /**< @brief iterator pointing to the first element of the vector */
  57.  
  58. public:
  59. 	CCompareWithOffset(typename std::vector<CScalar>::iterator p_begin_it)
  60. 		:m_p_begin_it(p_begin_it)
  61. 	{}
  62.  
  63. 	inline bool operator ()(const CScalar &r_value, TNeedle<CScalar> n) const
  64. 	{
  65. 		size_t n_index = &r_value - &*m_p_begin_it;
  66. 		// calculate index in the array
  67.  
  68. 		return r_value < n.n + n_index;
  69. 	}
  70.  
  71. 	inline bool operator ()(TNeedle<CScalar> n, const CScalar &r_value) const
  72. 	{
  73. 		size_t n_index = &r_value - &*m_p_begin_it;
  74. 		// calculate index in the array
  75.  
  76. 		return n.n + n_index < r_value;
  77. 	}
  78. };
  79.  
  80. namespace std {
  81.  
  82. template <class RanIt, class V>
  83. void iota(RanIt b, RanIt e, V counter)
  84. {
  85. 	if(b >= e)
  86. 		return;
  87. 	for(; b != e; ++ b, ++ counter)
  88. 		*b = counter;
  89. }
  90.  
  91. }
  92. // inject iota for old tyme people
  93.  
  94. static void RandomUniqueSequence(std::vector<int> &rand_num, const size_t n_number_num, const size_t n_item_num)
  95. {
  96. 	assert(n_number_num <= n_item_num);
  97.  
  98. 	rand_num.clear(); // !!
  99. #if 0
  100. 	// b1: 20250.000 msec
  101. 	// b2: 2296.000 msec
  102. 	std::set<int> numbers;
  103. 	while(numbers.size() < n_number_num)
  104. 		numbers.insert(n_Rand(n_item_num - 1)); // might have duplicates here
  105. 	// generate unique random numbers
  106.  
  107. 	rand_num.resize(numbers.size());
  108. 	std::copy(numbers.begin(), numbers.end(), rand_num.begin());
  109. 	// copy the numbers from a set to a list
  110. #elif 0
  111. 	// b1: 519515.000 msec
  112. 	// b2: 20312.000 msec
  113. 	std::vector<int> all_numbers(n_item_num);
  114. 	std::iota(all_numbers.begin(), all_numbers.end(), 0);
  115. 	// generate all the numbers
  116.  
  117. 	for(size_t i = 0; i < n_number_num; ++ i) {
  118. 		assert(all_numbers.size() == n_item_num - i);
  119. 		int n = n_Rand(n_item_num - i - 1);
  120. 		// get a random number
  121.  
  122. 		rand_num.push_back(all_numbers[n]); // put it in the output list
  123. 		all_numbers.erase(all_numbers.begin() + n); // erase it from the input
  124. 	}
  125. 	// generate random numbers
  126. #elif 0
  127. 	// b1: 2391.000 msec | 3187.000 msec (the fastest)
  128. 	// b2: 51484.000 msec | 3734.000 msec
  129. 	// b3: 5000.000 msec (10), 1172.000 msec (20), 3906.000 msec (50), 6938.000 msec (75), 10984.000 msec (100)
  130. 	for(size_t i = 0; i < n_number_num; ++ i) {
  131. 		int n = n_Rand(n_item_num - i - 1);
  132. 		// get a random number
  133.  
  134. 		size_t n_where = i;
  135. 		for(size_t j = 0; j < i; ++ j) {
  136. 			if(n >= rand_num[j])
  137. 				++ n;
  138. 			else {
  139. 				n_where = j;
  140. 				break;
  141. 			}
  142. 		}
  143. 		// see where it should be inserted
  144.  
  145. 		rand_num.insert(rand_num.begin() + n_where, 1, n);
  146. 		// insert it in the list, maintain a sorted sequence
  147. 	}
  148. 	// tier 0 - naive algorithm
  149. #elif 0
  150. 	// b1: 2391.000 msec | 3312.000 msec (the fastest)
  151. 	// b2: 51406.000 msec | 4218.000 msec
  152. 	for(size_t i = 0; i < n_number_num; ++ i) {
  153. 		int n = n_Rand(n_item_num - i - 1);
  154. 		// get a random number
  155.  
  156. 		size_t n_where = i;
  157. 		for(size_t j = 0; j < i; ++ j) {
  158. 			if(n + j < rand_num[j]) {
  159. 				n_where = j;
  160. 				break;
  161. 			}
  162. 		}
  163. 		// see where it should be inserted
  164.  
  165. 		rand_num.insert(rand_num.begin() + n_where, 1, n + n_where);
  166. 		// insert it in the list, maintain a sorted sequence
  167. 	}
  168. 	// tier 1 - use comparison with offset instead of increment
  169. #elif 0
  170. 	// b1: 3047.000 msec | 3750.000 msec
  171. 	// b2: 99375.000 msec | 5828.000 msec
  172. 	//rand_num.reserve(n_number_num); // makes it slightly slower
  173. 	for(size_t i = 0; i < n_number_num; ++ i) {
  174. 		int n = n_Rand(n_item_num - i - 1);
  175. 		// get a random number
  176.  
  177. 		size_t n_where = i;
  178. 		for(size_t j = 0; j < i; ++ j) {
  179. 			if(n /*+ j*/ < rand_num[j] /*+ j*/) {
  180. 				n_where = j;
  181. 				break;
  182. 			}
  183. 		}
  184. 		// see where it should be inserted
  185.  
  186. 		rand_num.insert(rand_num.begin() + n_where, 1, n); // each number encoded as value + its index
  187. 		// insert it in the list, maintain a sorted sequence
  188.  
  189. 		for(size_t j = n_where + 1; j <= i; ++ j)
  190. 			-- rand_num[j];
  191. 		// compensate for insertion in the middle
  192. 	}
  193. 	for(size_t i = 1; i < n_number_num; ++ i)
  194. 		rand_num[i] += i; // convert value + its index to absolute values
  195. 	// tier 2 - use offset encoding
  196. #elif 0
  197. 	// b1: 4078.000 msec | 3781.000 msec
  198. 	// b2: 33812.000 msec | 3203.000 msec
  199. 	rand_num.reserve(n_number_num); // don't want insertion invalidating the iterators
  200. 	for(size_t i = 0; i < n_number_num; ++ i) {
  201. 		int n = n_Rand(n_item_num - i - 1);
  202. 		// get a random number
  203.  
  204. 		std::vector<int>::iterator p_where_it = std::upper_bound(rand_num.begin(), rand_num.end(), n);
  205. 		// see where it should be inserted
  206.  
  207. 		rand_num.insert(p_where_it, 1, n); // each number encoded as value + its index
  208. 		assert(*p_where_it == n); // make sure the iterator was not invalidated (if it were, this would potentially trigger a different assertion in the iterator dereference, or crash the program depending on the STL implementation)
  209. 		// insert it in the list, maintain a sorted sequence
  210.  
  211. 		//struct Dec { void operator ()(int &r_n) const { -- r_n; } }; // above
  212. 		std::for_each(++ p_where_it, rand_num.end(), Dec());
  213. 		// compensate for insertion in the middle
  214. 	}
  215. 	for(size_t i = 1; i < n_number_num; ++ i)
  216. 		rand_num[i] += i; // convert value + its index to absolute values
  217. 	// tier 3 - use binary search with offset encoding
  218. #elif 1
  219. 	// b1: 4063.000 msec | 3578.000
  220. 	// b2: 12907.000 msec | 1703.000 msec (the fastest)
  221. 	// b3: 5656.000 msec (10), 1344.000 msec (20), 4172.000 (50), 6969.000 msec (75), 10094.000 msec (100)
  222. 	for(size_t i = 0; i < n_number_num; ++ i) {
  223. 		int n = n_Rand(n_item_num - i - 1);
  224. 		// get a random number
  225.  
  226. 		std::vector<int>::iterator p_where_it = std::upper_bound(rand_num.begin(), rand_num.end(),
  227. 			TNeedle<int>(n), CCompareWithOffset<int>(rand_num.begin()));
  228. 		// see where it should be inserted
  229.  
  230. 		rand_num.insert(p_where_it, 1, n + (p_where_it - rand_num.begin())); // msvc goes crazy without the parens
  231. 		// insert it in the list, maintain a sorted sequence
  232. 	}
  233. 	// tier 4 - use binary search
  234.  
  235. 	// this does binary search with the comparison "n + j < rand_num[j]" with non-constant needle,
  236. 	// which can be rewritten to one with constant needle and a modified sequence "n < rand_num[j] - j".
  237. 	// it is easily shown that since the lowest distance between two elements of the original
  238. 	// sequence "rand_num[j]" is:
  239. 	//
  240. 	//		rand_num[j] - rand_num[j - 1] >= 1
  241. 	//
  242. 	// (the generated numbers are unique), and at the same time, the difference
  243. 	// between different indices of "-j" is:
  244. 	//
  245. 	//		-j - -(j - 1) = -1
  246. 	//
  247. 	// The difference between elements of their sum "rand_num[j] - j" is:
  248. 	//
  249. 	//		(rand_num[j] - j) - (rand_num[j - 1] - (j - 1)) >= 0
  250. 	//
  251. 	// therefore, the sequence is nondecreasing and this comparison can be used.
  252. #endif // 0
  253. }
  254.  
  255. int main(int n_arg_num, const char **p_arg_list)
  256. {
  257. 	srand(int(time(0)));
  258.  
  259. 	const size_t n_number_num = 3;
  260. 	const size_t n_item_num = 7;
  261. 	std::vector<int> rand_num;
  262.  
  263. 	std::vector<size_t> histogram(n_item_num);
  264. 	for(size_t n_pass = 0; n_pass < 10000; ++ n_pass) {
  265. 		RandomUniqueSequence(rand_num, n_number_num, n_item_num);
  266.  
  267. 		assert(rand_num.size() == n_number_num); // make sure we generated all the numbers
  268. 		for(size_t i = 0, n = rand_num.size(); i < n; ++ i)
  269. 			assert(rand_num[i] >= 0 && size_t(rand_num[i]) < n_item_num); // make sure the numbers are in range
  270. 		std::sort(rand_num.begin(), rand_num.end());
  271. 		assert(std::unique(rand_num.begin(), rand_num.end()) == rand_num.end()); // make sure the numbers are unique
  272. 		// debug checks
  273.  
  274. 		for(size_t i = 0, n = rand_num.size(); i < n; ++ i)
  275. 			++ histogram[rand_num[i]];
  276. 		// accumulate histograms to see the distribution
  277. 	}
  278.  
  279. 	printf("histogram over many iterations:\n");
  280. 	std::for_each(histogram.begin(), histogram.end(), &Print);
  281. 	printf("\n");
  282.  
  283. 	double t = GetTickCount() * 1e-3;
  284.  
  285. 	/*for(size_t n_pass = 0; n_pass < 10000000; ++ n_pass) {
  286. 		const size_t n_number_num = 7;
  287. 		const size_t n_item_num = 5000;
  288. 		RandomUniqueSequence(rand_num, n_number_num, n_item_num);
  289. 	}*/
  290. 	// benchmark 1
  291.  
  292. 	for(size_t n_pass = 0; n_pass < 10000; ++ n_pass) {
  293. 		const size_t n_number_num = 700;
  294. 		const size_t n_item_num = 5000;
  295. 		RandomUniqueSequence(rand_num, n_number_num, n_item_num);
  296. 	}
  297. 	// benchmark 2
  298.  
  299. 	/*for(size_t n_pass = 0; n_pass < 1000000; ++ n_pass) {
  300. 		const size_t n_number_num = 75;
  301. 		const size_t n_item_num = 1000;
  302. 		RandomUniqueSequence(rand_num, n_number_num, n_item_num);
  303. 	}*/
  304. 	// benchmark 3
  305.  
  306. 	t = GetTickCount() * 1e-3 - t;
  307.  
  308. 	printf("done. it took %.3f msec\n", t * 1000);
  309.  
  310. 	return 0;
  311. }
  312.  
Success #stdin #stdout 1.65s 3432KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
histogram over many iterations:
4366 4340 4167 4307 4281 4231 4308 
done. it took 1640.000 msec
https://ideone.com/Ra3b2v
language:
C++ (gcc 8.3)
created:
9 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!