fork(7) download 
  1. /* Hack of earlier code to compare vectors worst-case towards linked-list best case
  2. I.e. 1) insertion of x elements at first position
  3.      1b) The same but do for vector at last position
  4. */
  5.  
  6. #include <list>
  7. #include <vector>
  8. #include <iostream>
  9. #include <iomanip>
  10. #include <functional>
  11. #include <random>
  12. #include <iostream>
  13. #include <chrono>
  14. #include <string>
  15. #include <numeric>
  16. #include <algorithm>
  17. #include <cassert>
  18.  
  19. namespace g2
  20. {       
  21.   typedef std::chrono::high_resolution_clock clock;
  22.   typedef std::chrono::microseconds microseconds;
  23.   typedef std::chrono::milliseconds milliseconds;
  24.  
  25.   clock::time_point now(){return clock::now();}
  26.  
  27.   microseconds intervalUs(const clock::time_point& t1, const clock::time_point& t0)
  28.   {return std::chrono::duration_cast<microseconds>(t1 - t0);}
  29.  
  30.   milliseconds intervalMs(const clock::time_point& t1,const clock::time_point& t0)
  31.   {return std::chrono::duration_cast<milliseconds>(t1 - t0);}
  32.  
  33.  
  34.   class StopWatch
  35.   {
  36.     clock::time_point start_;
  37.   public:
  38.     StopWatch() : start_(clock::now()){}
  39.     clock::time_point restart()         { start_ = clock::now(); return start_;}
  40.     microseconds elapsedUs()            { return intervalUs(now(), start_);}
  41.     milliseconds elapsedMs()            {return intervalMs(now(), start_);}
  42.   };
  43. } // g2
  44.  
  45.  
  46. typedef unsigned int  Number;
  47. typedef std::list<Number>           NumbersInList;
  48. typedef std::vector<Number>         NumbersInVector;
  49. typedef long long int               TimeValue;
  50.  
  51.  
  52. int random_int(int low, int high)
  53. {
  54.   using namespace std;
  55.   static default_random_engine engine;
  56.   typedef uniform_int_distribution<int> Distribution;
  57.   static Distribution distribution;
  58.   return distribution(engine, Distribution::param_type(low, high));
  59. }
  60. template<typename Container>
  61. void firstPositionInsertion(const NumbersInVector& numbers, Container& container)
  62. {
  63.     std::for_each(numbers.begin(), numbers.end(),
  64.                   [&](const Number& n)
  65.     {
  66.         auto itr = container.begin();
  67.         container.insert(itr, n);
  68.     });
  69. }
  70.  
  71. // For vector, push always at back position
  72. TimeValue lastPositionInsertionPerformance(const NumbersInVector& numbers, 
  73.                                             NumbersInVector& vector)
  74. {
  75.     g2::StopWatch watch;
  76.     std::for_each(numbers.begin(), numbers.end(),
  77.                   [&](const Number& n)
  78.     {
  79. 	    vector.push_back(n);
  80.     });
  81.  
  82. 	auto time = watch.elapsedUs().count();
  83.     return time;
  84. }
  85.  
  86.  
  87. // Measure time in milliseconds for linear insert in a std container
  88. template<typename Container>
  89. TimeValue linearInsertPerformance(const NumbersInVector& randoms, Container& container)
  90. {
  91.     g2::StopWatch watch;
  92.     firstPositionInsertion(std::cref(randoms), container);
  93.     auto time = watch.elapsedUs().count();
  94.     return time;
  95. }
  96.  
  97.  
  98.  
  99. void addPerformance(size_t nbr_of_randoms)
  100. {
  101.   // Generate n random values and push to storage
  102.   NumbersInVector     values(nbr_of_randoms);
  103.   std::for_each(values.begin(), values.end(), [&](Number& n) { n = random_int(0, nbr_of_randoms -1);}); 
  104.  
  105.   NumbersInVector vector_worst;
  106.   NumbersInVector vector_best;
  107.   NumbersInList   list;
  108.  
  109.  
  110.   std::cout << nbr_of_randoms << ",  " << std::flush;
  111.   TimeValue list_time = linearInsertPerformance(values, list);
  112.   TimeValue vector_best_time = lastPositionInsertionPerformance(values, vector_best);
  113.   TimeValue vector_worst_time = linearInsertPerformance(values, vector_worst);
  114.   std::cout << list_time << ", " << vector_best_time << ", " << vector_worst_time << " " << std::endl << std::flush;
  115. }
  116.  
  117.  
  118.  
  119.  
  120.  
  121.  
  122. int main(int argc, char** argv)
  123. { 
  124.  
  125.   std::cout << "Perhaps the most common 'data collecting' operation is putting 'one piece of data" << std::endl;
  126.   std::cout << "  in front of an older piece of data and so forth.\n" << std::endl; 
  127.   std::cout << "For linked-list this is insertion at index 0\n" << std::endl;
  128.   std::cout << "For std::vector  the 'push at front' operation is working against nature of the " << std::endl;
  129.   std::cout  << "  data structure and in this common scenario such use is called 'naive'\n" << std::endl;
  130.   std::cout << "For std::vector it is natural in this scenario to work in the direction of 'growth' " << std::endl; 
  131.   std::cout << "i.e. push_back. It solves the same task but works as intended with the nature of the " << std::endl; 
  132.   std::cout << "  data structure.\n\n" << std::endl; 
  133.  
  134.   std::cout << "elements, list, vector_best, vector_worst(naive)" << std::endl;
  135.   g2::StopWatch watch;
  136.   addPerformance(10);
  137.   addPerformance(100);
  138.   addPerformance(500);
  139.   addPerformance(1000);
  140.   addPerformance(2000);
  141.   addPerformance(10000);
  142.   addPerformance(20000);
  143.   addPerformance(40000);
  144.   addPerformance(100000);
  145.   // more than this will timeout on ideone
  146.    // addPerformance(500000);
  147.   //addPerformance(1000000);
  148.  
  149.   auto total_time_ms = watch.elapsedMs().count();
  150.   std::cout << "Exiting test,. the whole measuring took " << total_time_ms << " milliseconds";
  151.   std::cout << " (" << total_time_ms/1000 << "seconds or " << total_time_ms/(1000*60) << " minutes)" << std::endl; 
  152.    return 0;
  153. }
Success #stdin #stdout 4.2s 3068KB
comments (?)
stdin 
Standard input is empty
stdout 
Perhaps the most common 'data collecting' operation is putting 'one piece of data
  in front of an older piece of data and so forth.

For linked-list this is insertion at index 0

For std::vector  the 'push at front' operation is working against nature of the 
  data structure and in this common scenario such use is called 'naive'

For std::vector it is natural in this scenario to work in the direction of 'growth' 
i.e. push_back. It solves the same task but works as intended with the nature of the 
  data structure.


elements, list, vector_best, vector_worst(naive)
10,  3, 6, 1 
100,  7, 3, 13 
500,  43, 7, 83 
1000,  70, 10, 285 
2000,  149, 27, 986 
10000,  928, 159, 22613 
20000,  1578, 284, 97330 
40000,  3138, 582, 553636 
100000,  7802, 1179, 3555756 
Exiting test,. the whole measuring took 4266 milliseconds (4seconds or 0 minutes)
https://ideone.com/DDEJF
language:
C++14 (gcc 8.3)
created:
12 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!