fork(2) download
  1. /* SMART Linked-list vs "normal" linked-list vs Vector. 15seconds maximum run-time
  2. Linear search and sorted insertion. std::list remembers last position to
  3. minimize overhead in traversing the list.*/
  4.  
  5. #include <list>
  6. #include <vector>
  7. #include <iostream>
  8. #include <iomanip>
  9. #include <random>
  10. #include <functional>
  11. #include <iostream>
  12. #include <chrono>
  13. #include <string>
  14. #include <numeric>
  15. #include <algorithm>
  16. #include <cassert>
  17.  
  18. namespace g2
  19. {
  20. typedef std::chrono::high_resolution_clock clock;
  21. typedef std::chrono::microseconds microseconds;
  22. typedef std::chrono::milliseconds milliseconds;
  23.  
  24. clock::time_point now(){return clock::now();}
  25.  
  26. microseconds intervalUs(const clock::time_point& t1, const clock::time_point& t0)
  27. {return std::chrono::duration_cast<microseconds>(t1 - t0);}
  28.  
  29. milliseconds intervalMs(const clock::time_point& t1,const clock::time_point& t0)
  30. {return std::chrono::duration_cast<milliseconds>(t1 - t0);}
  31.  
  32.  
  33. class StopWatch
  34. {
  35. clock::time_point start_;
  36. public:
  37. StopWatch() : start_(clock::now()){}
  38. clock::time_point restart() { start_ = clock::now(); return start_;}
  39. microseconds elapsedUs() { return intervalUs(now(), start_);}
  40. milliseconds elapsedMs() {return intervalMs(now(), start_);}
  41. };
  42. } // g2
  43.  
  44.  
  45.  
  46.  
  47.  
  48. typedef unsigned int Number;
  49. typedef std::list<Number> NumbersInList;
  50. typedef std::vector<Number> NumbersInVector;
  51. typedef long long int TimeValue;
  52.  
  53.  
  54. /* // Lambda expression for generating a random number using the 'mersenne twister distribution'
  55.   // http://en.wikipedia.org/wiki/Mersenne_twister
  56. auto random_int = [&](const Number& low, const Number& high) -> Number {
  57.   std::uniform_int_distribution<int> distribution(low, high);
  58.   std::mt19937 engine((unsigned int)time(0)); // Mersenne twister MT19937
  59.   auto generator = std::bind(distribution, engine);
  60.   return generator();
  61. }; */
  62.  
  63. // Random integer function from http://www2.research.att.com/~bs/C++0xFAQ.html#std-random
  64. int random_int(int low, int high)
  65. {
  66. using namespace std;
  67.  
  68. static default_random_engine engine {};
  69. typedef uniform_int_distribution<int> Distribution;
  70. static Distribution distribution {};
  71.  
  72. return distribution(engine, Distribution::param_type{low, high});
  73. }
  74.  
  75.  
  76.  
  77.  
  78.  
  79.  
  80. // Use a template approach to use functor, function pointer or lambda to insert an
  81. // element in the input container and return the "time result".
  82. // Search is LINEAR. Elements are insert in SORTED order
  83. template<typename Container>
  84. void linearInsertion(const NumbersInVector& numbers, Container& container)
  85. {
  86. std::for_each(numbers.begin(), numbers.end(),
  87. [&](const Number& n)
  88. {
  89. auto itr = container.begin();
  90. for (; itr!= container.end(); ++itr)
  91. {
  92. if ((*itr) >= n) {
  93. break;
  94. }
  95. }
  96. container.insert(itr, n);
  97. });
  98. }
  99.  
  100. namespace{
  101. // A little bit smarter --- remembers the last insertion point's position and can
  102. // start from that if wanted-position is >= last-position: this is calculated from the values
  103. // and not from the absolute positions
  104. TimeValue linearSmartInsertPerformance(const NumbersInVector& numbers, NumbersInList& container)
  105. {
  106. g2::StopWatch watch;
  107. auto last_inserted_value = 0;
  108. auto last_iter_position = container.begin();
  109.  
  110. std::for_each(numbers.begin(), numbers.end(),
  111. [&](const Number& n)
  112. {
  113. auto itr = container.begin();
  114. if(n >= last_inserted_value)
  115. {
  116. itr = last_iter_position;
  117. }
  118.  
  119. for (; itr!= container.end(); ++itr)
  120. {
  121. if ((*itr) >= n) {
  122. break;
  123. }
  124. }
  125. last_iter_position = container.insert(itr, n);
  126. last_inserted_value = n;
  127. });
  128. auto time = watch.elapsedUs().count();
  129. return time;
  130. }
  131. } // anonymous namespace
  132.  
  133. // Measure time in milliseconds for linear insert in a std container
  134. template<typename Container>
  135. TimeValue linearInsertPerformance(const NumbersInVector& randoms, Container& container)
  136. {
  137. g2::StopWatch watch;
  138. linearInsertion(std::cref(randoms), container);
  139. auto time = watch.elapsedUs().count();
  140. return time;
  141. }
  142.  
  143.  
  144. void listVsVectorLinearPerformance(size_t nbr_of_randoms)
  145. {
  146. // Generate n random values and push to storage
  147. NumbersInVector values(nbr_of_randoms);
  148. std::for_each(values.begin(), values.end(), [&](Number& n) { n = random_int(0, nbr_of_randoms -1);});
  149. //print_distribution(values);
  150.  
  151. TimeValue smarter_list_time;
  152. TimeValue list_time;
  153. TimeValue vector_time;
  154. std::cout << nbr_of_randoms << ",\t" << std::flush;
  155.  
  156.  
  157. { // force local scope - to clear up the containers at exit
  158. NumbersInList list;
  159. smarter_list_time = linearSmartInsertPerformance(values, list);
  160. }
  161. {
  162. NumbersInList list;
  163. list_time = linearInsertPerformance(values, list);
  164. }
  165. {
  166. NumbersInVector vector;
  167. vector_time = linearInsertPerformance(values, vector);
  168. std::cout << " " << ", ";
  169. }
  170. std::cout << smarter_list_time << ", " << list_time << ", " << vector_time << std::endl << std::flush;
  171. }
  172.  
  173.  
  174. int main(int argc, char** argv)
  175. {
  176.  
  177. std::cout << "\n\n********** Times in microseconds**********" << std::endl;
  178. std::cout << "Elements ADD (Smarter-List, List, Vector)" << std::endl;
  179.  
  180. g2::StopWatch watch; // only 15seconds available, therefore the short ranges
  181. listVsVectorLinearPerformance(10);
  182. listVsVectorLinearPerformance(100);
  183. listVsVectorLinearPerformance(500);
  184. listVsVectorLinearPerformance(1000);
  185. listVsVectorLinearPerformance(2000);
  186. listVsVectorLinearPerformance(3000);
  187. listVsVectorLinearPerformance(4000);
  188. listVsVectorLinearPerformance(6000);
  189. listVsVectorLinearPerformance(8000);
  190. listVsVectorLinearPerformance(16000);
  191. listVsVectorLinearPerformance(32000);
  192. auto total_time_ms = watch.elapsedMs().count();
  193.  
  194. std::cout << "Exiting test,. the whole measuring took " << total_time_ms << " milliseconds";
  195. std::cout << " (" << total_time_ms/1000 << "seconds or " << total_time_ms/(1000*60) << " minutes)" << std::endl;
  196. return 0;
  197. }
Success #stdin #stdout 5.32s 3600KB
stdin
Standard input is empty
stdout

********** Times in microseconds**********
Elements ADD (Smarter-List,   List,    Vector)
10,	 , 3, 1, 2
100,	 , 11, 9, 18
500,	 , 116, 103, 184
1000,	 , 375, 374, 612
2000,	 , 1353, 1416, 2312
3000,	 , 2989, 3362, 5126
4000,	 , 5128, 5799, 8970
6000,	 , 15525, 31914, 20208
8000,	 , 37300, 73428, 35747
16000,	 , 229193, 423143, 142945
32000,	 , 1292174, 2393017, 608935
Exiting test,. the whole measuring took 5351 milliseconds (5seconds or 0 minutes)