fork(5) download 
  1. #include <chrono>
  2. #include <ctime>
  3. #include <type_traits>
  4. #include <tuple>
  5. #include <iostream>
  6. #include <algorithm>
  7. #include <functional>
  8. #include "smoothsort.h"
  9. #include "timsort.h"
  10.  
  11. // http://b...content-available-to-author-only...r.ca/2012/05/13/timing-functions-with-chrono.html
  12. template <typename Clock, typename Func>
  13. inline typename Clock::duration time_function(Func&& f)
  14. {
  15. 	auto start_time = Clock::now();
  16. 	f();
  17. 	auto time_taken = Clock::now() - start_time;
  18. 	return time_taken;
  19. }
  20.  
  21. enum state_t
  22. {
  23.     sorted, randomized, reversed, partially_sorted_0, partially_sorted_1
  24. };
  25.  
  26. template <typename value_t>
  27. static void bench(int const size, state_t const state)
  28. {
  29. 	typedef std::chrono::high_resolution_clock clock_type;
  30.  
  31. 	std::cerr << "size\t" << size << std::endl;
  32.  
  33. 	std::less<value_t> lt;
  34. 	std::greater<value_t> gt;
  35.  
  36. 	std::vector<value_t> a;
  37. 	for(int i = 0; i < size; ++i)
  38. 	{
  39. 		a.push_back((i+1) * 10);
  40. 	}
  41.  
  42. 	switch(state)
  43. 	{
  44. 	case randomized:
  45. 		std::random_shuffle(a.begin(), a.end());
  46. 		break;
  47. 	case reversed:
  48. 		std::reverse(a.begin(), a.end());
  49. 		break;
  50. 	case sorted:
  51. 		break;
  52. 	case partially_sorted_0:
  53. 		{
  54. 		std::random_shuffle(a.begin(), a.end());
  55. 		bool toggle = true;
  56. 		for(auto i=a.begin(); i < a.end(); i+=10)
  57. 		{
  58. 			if(toggle)
  59. 				std::stable_sort(i, i+10, lt);
  60. 			else
  61. 				std::stable_sort(i, i+10, gt);
  62. 			toggle = !toggle;
  63. 		}
  64. 		}
  65. 		break;
  66. 	case partially_sorted_1:
  67. 		{
  68. 		std::random_shuffle(a.begin(), a.end());
  69. 		bool toggle = true;
  70. 		for(auto i=a.begin(); i < a.end(); i+=1000)
  71. 		{
  72. 			if(toggle)
  73. 				std::stable_sort(i, i+1000, lt);
  74. 			else
  75. 				std::stable_sort(i, i+1000, gt);
  76. 			toggle = !toggle;
  77. 		}
  78. 		}
  79. 		break;
  80. 	default:
  81. 		assert(!"not reached");
  82. 	}
  83.  
  84. 	{
  85. 		std::vector<value_t> b(a);
  86.  
  87. 		auto duration = time_function<clock_type>([&]
  88. 		{
  89. 			for(int i = 0; i < 100; ++i) 
  90. 			{
  91. 				std::copy(a.begin(), a.end(), b.begin());
  92. 				std::sort(b.begin(), b.end(), lt);
  93.       }
  94. 		});
  95.  
  96. 		std::cerr << "std::sort " << std::chrono::duration_cast<std::chrono::milliseconds>(duration).count() << " ms" << std::endl;
  97. 	}
  98.  
  99. 	{
  100. 		std::vector<value_t> b(a);
  101.  
  102. 		auto duration = time_function<clock_type>([&]
  103. 		{
  104. 			for(int i = 0; i < 100; ++i) 
  105. 			{
  106. 				std::copy(a.begin(), a.end(), b.begin());
  107. 				std::stable_sort(b.begin(), b.end(), lt);
  108.       }
  109. 		});
  110.  
  111. 		std::cerr << "std::stable_sort " << std::chrono::duration_cast<std::chrono::milliseconds>(duration).count() << " ms" << std::endl;
  112. 	}
  113.  
  114. 	{
  115. 		std::vector<value_t> b(a);
  116.  
  117. 		auto duration = time_function<clock_type>([&]
  118. 		{
  119. 			for(int i = 0; i < 100; ++i) 
  120. 			{
  121. 				std::copy(a.begin(), a.end(), b.begin());
  122. 				Smoothsort(b.begin(), b.end(), lt);
  123.       }
  124. 		});
  125.  
  126. 		std::cerr << "smoothsort " << std::chrono::duration_cast<std::chrono::milliseconds>(duration).count() << " ms" << std::endl;
  127. 	}
  128.  
  129. 	{
  130. 		std::vector<value_t> b(a);
  131.  
  132. 		auto duration = time_function<clock_type>([&]
  133. 		{
  134. 			for(int i = 0; i < 100; ++i) 
  135. 			{
  136. 				std::copy(a.begin(), a.end(), b.begin());
  137. 				timsort(b.begin(), b.end(), lt);
  138.       }
  139. 		});
  140.  
  141. 		std::cerr << "timsort " << std::chrono::duration_cast<std::chrono::milliseconds>(duration).count() << " ms" << std::endl;
  142. 	}
  143. }
  144.  
  145. static void doit(int const n, state_t const state) {
  146.     std::cerr << "int" << std::endl;
  147.     bench<int>(n, state);
  148.  
  149.     std::cerr << "double" << std::endl;
  150.     bench<double>(n, state);
  151. }
  152.  
  153. int main(int argc, char* argv[])
  154. {
  155.  
  156.  
  157. 	const int N = 1000*100;
  158.  
  159. 	std::srand(static_cast<unsigned int>(std::time(NULL)));
  160.  
  161. 	std::cout << "RANDOMIZED SEQUENCE" << std::endl;
  162. 	doit(N, randomized);
  163. 	std::cout << std::endl;
  164.  
  165. 	std::cout << "REVERSED SEQUENCE" << std::endl;
  166. 	doit(N, reversed);
  167. 	std::cout << std::endl;
  168.  
  169. 	std::cout << "SORTED SEQUENCE" << std::endl;
  170. 	doit(N, sorted);
  171. 	std::cout << std::endl;
  172.  
  173. 	std::cout << "PARTIALLY SORTED SEQUENCE 0" << std::endl;
  174. 	doit(N, partially_sorted_0);
  175. 	std::cout << std::endl;
  176.  
  177. 	std::cout << "PARTIALLY SORTED SEQUENCE 1" << std::endl;
  178. 	doit(N, partially_sorted_1);
  179. 	std::cout << std::endl;
  180.  
  181. 	return 0;
  182. }
Not running #stdin #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/SCRI6
language:
C++14 (gcc 8.3)
created:
12 years ago
visibility:
secret

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!