fork(9) download
copy 
  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://e...content-available-to-author-only...a.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://w...content-available-to-author-only...t.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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 

********** 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)
https://ideone.com/XprUU
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!