fork download 
  1. #include <iostream>
  2. #include <random>
  3. #include <cstring>
  4. typedef unsigned int uint32;
  5.  
  6. const uint32 arrSize = 500;
  7.  
  8. uint32 myRandom()
  9. {
  10. 	static thread_local std::mt19937 prng(std::random_device{}());
  11. 	static thread_local std::uniform_int_distribution<uint32> dist(0u, arrSize-1u);
  12.  
  13. 	return dist(prng);
  14. }
  15.  
  16. int main()
  17. {
  18. 	bool* arr = new bool[arrSize];
  19. 	uint32 steps = 0;
  20. 	const int numIter = 100;
  21. 	for (int i = 0; i < numIter; ++i)
  22. 	{
  23. 		int numFilled = 0;
  24. 		memset(arr, 0, arrSize * sizeof(bool));
  25.  
  26. 		while (numFilled < arrSize)
  27. 		{
  28. 			uint32 r = myRandom();
  29. 			if (!arr[r])
  30. 			{
  31. 				arr[r] = true;
  32. 				++numFilled;
  33. 			}
  34. 			++steps;
  35. 		}
  36. 	}
  37.  
  38. 	std::cout << "Steps: " << double(steps)/double(numIter) << "\t nlogn: " << double(arrSize)*log(double(arrSize)) << "\n";
  39.  
  40. 	return 0;
  41. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin 
Standard input is empty
stdout 
Steps: 3390.55	 nlogn: 3107.3
https://ideone.com/5Vgi10
language:
C++14 (gcc 8.3)
created:
6 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!