fork download
copy 
  1. #include <iostream>
  2. #include <string>
  3. #include <chrono>
  4. #include <ctime>
  5. #include <array>
  6.  
  7. #define onlyAtEnd(a) typename std::enable_if<sizeof...(a) == 0 > ::type
  8.  
  9. template<int a, int b>
  10. class Entry
  11. {
  12. public:
  13. 	static constexpr int VAL = a;
  14. 	static constexpr int PROB = b;
  15. };
  16.  
  17. template<typename... EntryTypes>
  18. class NumChooser
  19. {
  20. private:
  21. 	const int SUM;
  22. 	static constexpr int NUM_VALS = sizeof...(EntryTypes);
  23.  
  24. public:
  25.  
  26. 	static constexpr int size()
  27. 	{
  28. 		return NUM_VALS;
  29. 	}
  30.  
  31. 	template<typename T, typename... args>
  32. 	constexpr int calcSum()
  33. 	{
  34. 		return T::PROB + calcSum < args...>();
  35. 	}
  36.  
  37. 	template <typename... Ts, typename = onlyAtEnd(Ts) >
  38. 	constexpr int calcSum()
  39. 	{
  40. 		return 0;
  41. 	}
  42.  
  43. 	NumChooser() : SUM(calcSum < EntryTypes... >()) { }
  44.  
  45. 	template<typename T, typename... args>
  46. 	constexpr int find(int left, int previous = 0)
  47. 	{
  48. 		return left < 0 ? previous : find < args... >(left - T::PROB, T::VAL);
  49. 	}
  50.  
  51. 	template <typename... Ts, typename = onlyAtEnd(Ts) >
  52. 	constexpr int find(int left, int previous)
  53. 	{
  54. 		return previous;
  55. 	}
  56.  
  57. 	constexpr int choose()
  58. 	{
  59. 		return find < EntryTypes... >(1 + (rand() % SUM));
  60. 	}
  61. };
  62.  
  63. NumChooser <
  64. Entry<0, 10>,
  65. Entry<1, 50>,
  66. Entry<2, 80>,
  67. Entry<3, 01>
  68. > chooser;
  69.  
  70. // Warning! The test code below is very hackish and not well crafted!
  71. int main()
  72. {
  73. 	srand(time(nullptr));
  74. 	std::array<int, chooser.size() > frequency{};
  75. 	const int NUM_AV = 50000; // How many trials to average
  76. 	const int NUM_TRIALS = 1000;
  77.  
  78. 	std::chrono::time_point<std::chrono::system_clock> start, end;
  79. 	std::chrono::duration<double> elapsed;
  80.  
  81. 	double templateTime = 0;
  82. 	for (int av = 0; av < NUM_AV; ++av)
  83. 	{
  84. 		start = std::chrono::system_clock::now();
  85. 		for (int i = 0; i < NUM_TRIALS; ++i)
  86. 			frequency[chooser.choose()]++;
  87. 		end = std::chrono::system_clock::now();
  88. 		elapsed = end-start;
  89. 		double time = elapsed.count();
  90. 		templateTime = (av*templateTime + time) / (av + 1);
  91. 		if ((NUM_AV/100) < 1 || av % (NUM_AV/100)==0)
  92. 			std::cout << 100.0*av / (NUM_AV - 1) << "%" << std::endl;
  93. 	}
  94.  
  95. 	const int SUM = 141;
  96. 	const int VALS[] = {0,1,2,3};
  97. 	const int PROB[] = {10,50,80,01};
  98.  
  99. 	double basicTime = 0;
  100. 	int id, val;
  101. 	for (int av = 0; av < NUM_AV; ++av)
  102. 	{
  103. 		start = std::chrono::system_clock::now();
  104. 		for (int i = 0; i < NUM_TRIALS; ++i)
  105. 		{
  106. 			val = 1 + rand()%SUM;
  107. 			id = -1;
  108. 			do
  109. 			{
  110. 				++id;
  111. 				val -= PROB[id];
  112. 			}
  113. 			while(val>0);
  114. 			frequency[VALS[id]]++;
  115. 		}
  116. 		end = std::chrono::system_clock::now();
  117. 		elapsed = end-start;
  118. 		double t = elapsed.count();
  119. 		basicTime = (av * basicTime + t) / (av + 1);
  120. 		if ((NUM_AV/100) < 1 || av % (NUM_AV/100)==0)
  121. 			std::cout << 100.0*av / (NUM_AV - 1) << "%" << std::endl;
  122. 	}
  123.  
  124. 	std::cout << "Template based implementation:" << std::endl;
  125. 	std::cout << templateTime << std::endl;
  126.  
  127. 	std::cout << "Basic implementation:" << std::endl;
  128. 	std::cout << basicTime << std::endl;
  129.  
  130. 	double change = 100.0*(templateTime - basicTime) / basicTime;
  131. 	std::cout << "Template % change:" << std::endl;
  132. 	std::cout << change << std::endl;
  133. }
Success #stdin #stdout 2.5s 3460KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0%
1.00002%
2.00004%
3.00006%
4.00008%
5.0001%
6.00012%
7.00014%
8.00016%
9.00018%
10.0002%
11.0002%
12.0002%
13.0003%
14.0003%
15.0003%
16.0003%
17.0003%
18.0004%
19.0004%
20.0004%
21.0004%
22.0004%
23.0005%
24.0005%
25.0005%
26.0005%
27.0005%
28.0006%
29.0006%
30.0006%
31.0006%
32.0006%
33.0007%
34.0007%
35.0007%
36.0007%
37.0007%
38.0008%
39.0008%
40.0008%
41.0008%
42.0008%
43.0009%
44.0009%
45.0009%
46.0009%
47.0009%
48.001%
49.001%
50.001%
51.001%
52.001%
53.0011%
54.0011%
55.0011%
56.0011%
57.0011%
58.0012%
59.0012%
60.0012%
61.0012%
62.0012%
63.0013%
64.0013%
65.0013%
66.0013%
67.0013%
68.0014%
69.0014%
70.0014%
71.0014%
72.0014%
73.0015%
74.0015%
75.0015%
76.0015%
77.0015%
78.0016%
79.0016%
80.0016%
81.0016%
82.0016%
83.0017%
84.0017%
85.0017%
86.0017%
87.0017%
88.0018%
89.0018%
90.0018%
91.0018%
92.0018%
93.0019%
94.0019%
95.0019%
96.0019%
97.0019%
98.002%
99.002%
0%
1.00002%
2.00004%
3.00006%
4.00008%
5.0001%
6.00012%
7.00014%
8.00016%
9.00018%
10.0002%
11.0002%
12.0002%
13.0003%
14.0003%
15.0003%
16.0003%
17.0003%
18.0004%
19.0004%
20.0004%
21.0004%
22.0004%
23.0005%
24.0005%
25.0005%
26.0005%
27.0005%
28.0006%
29.0006%
30.0006%
31.0006%
32.0006%
33.0007%
34.0007%
35.0007%
36.0007%
37.0007%
38.0008%
39.0008%
40.0008%
41.0008%
42.0008%
43.0009%
44.0009%
45.0009%
46.0009%
47.0009%
48.001%
49.001%
50.001%
51.001%
52.001%
53.0011%
54.0011%
55.0011%
56.0011%
57.0011%
58.0012%
59.0012%
60.0012%
61.0012%
62.0012%
63.0013%
64.0013%
65.0013%
66.0013%
67.0013%
68.0014%
69.0014%
70.0014%
71.0014%
72.0014%
73.0015%
74.0015%
75.0015%
76.0015%
77.0015%
78.0016%
79.0016%
80.0016%
81.0016%
82.0016%
83.0017%
84.0017%
85.0017%
86.0017%
87.0017%
88.0018%
89.0018%
90.0018%
91.0018%
92.0018%
93.0019%
94.0019%
95.0019%
96.0019%
97.0019%
98.002%
99.002%
Template based implementation:
2.50881e-05
Basic implementation:
2.42774e-05
Template % change:
3.33935
https://ideone.com/S3GfUq
language:
C++14 (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!