fork download
copy 
  1. //
  2. // Comparison of sort. std::vector vs std::list
  3. //
  4.  
  5. #include <list>
  6. #include <vector>
  7. #include <iostream>
  8. #include <functional>
  9. #include <random>
  10. #include <iostream>
  11. #include <chrono>
  12. #include <string>
  13. #include <numeric>
  14. #include <algorithm>
  15.  
  16. namespace g2
  17. {       
  18.   typedef std::chrono::high_resolution_clock clock;
  19.   typedef std::chrono::microseconds microseconds;
  20.   typedef std::chrono::milliseconds milliseconds;
  21.  
  22.   clock::time_point now(){return clock::now();}
  23.  
  24.   microseconds intervalUs(const clock::time_point& t1, const clock::time_point& t0)
  25.   {return std::chrono::duration_cast<microseconds>(t1 - t0);}
  26.  
  27.   milliseconds intervalMs(const clock::time_point& t1,const clock::time_point& t0)
  28.   {return std::chrono::duration_cast<milliseconds>(t1 - t0);}
  29.  
  30.  
  31.   class StopWatch
  32.   {
  33.     clock::time_point start_;
  34.   public:
  35.     StopWatch() : start_(clock::now()){}
  36.     clock::time_point restart()         { start_ = clock::now(); return start_;}
  37.     microseconds elapsedUs()            { return intervalUs(now(), start_);}
  38.     milliseconds elapsedMs()            {return intervalMs(now(), start_);}
  39.   };
  40. } // g2
  41.  
  42.  
  43.  
  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. // Used for debugging and verification, 
  53. // normally disabled
  54. template<typename Container>
  55. void printValues(const std::string& msg, const Container& values)
  56. {
  57.   std::cout << msg << std::endl;
  58.   std::for_each(values.begin(), values.end(),
  59.     [&](const Number& n) { std::cout << " " << n << " "; }); 
  60.  
  61.   std::cout << "\n" << std::endl;
  62. }
  63.  
  64.  
  65.  
  66.  
  67. void listVsVectorSort(size_t nbr_of_randoms)
  68. {
  69.   std::uniform_int_distribution<int> distribution(0, nbr_of_randoms);
  70.   std::mt19937 engine((unsigned int)time(0)); // Mersenne twister MT19937
  71.   auto generator = std::bind(distribution, engine);
  72.   NumbersInVector  vector(nbr_of_randoms);
  73.   NumbersInList list;
  74.  
  75.   std::for_each(vector.begin(), vector.end(), [&](Number& n) { n = generator(); list.push_back(n); }    );
  76.   TimeValue list_time;
  77.   {  // list measure sort
  78.     g2::StopWatch watch;
  79.     list.sort();
  80.     list_time = watch.elapsedUs().count();
  81.   }
  82.     TimeValue vector_time;    
  83.   {  // vector measure sort
  84.     g2::StopWatch watch;
  85.     std::sort(vector.begin(), vector.end());
  86.     vector_time = watch.elapsedUs().count();
  87.   }
  88.  
  89.   std::cout <<  nbr_of_randoms << "\t\t, " << list_time << ", (" << (100*list_time/vector_time);
  90.   std::cout <<  "%),\t\t" << vector_time << " , (" << (100*vector_time/vector_time) << "%)" << std::endl;
  91. }
  92.  
  93.  
  94.  
  95.  
  96.  
  97.  
  98.  
  99. int main(int argc, char** argv)
  100. { 
  101. std::cout << "\n\n********** Times in microseconds (us) **********" << std::endl;
  102. std::cout << "Elements SORT(List, Vector)" << std::endl;
  103. std::cout <<  "elements\t, list_time\t, vector_time" << std::endl;
  104. g2::StopWatch watch;
  105.  
  106.        listVsVectorSort(10);
  107.        listVsVectorSort(1000);
  108.        listVsVectorSort(10000);
  109.        listVsVectorSort(100000);
  110.        listVsVectorSort(1000000);
  111.        listVsVectorSort(10000000);
  112.  
  113.   auto total_time_ms = watch.elapsedMs().count();
  114.   std::cout << "Exiting test,. the whole measuring took " << total_time_ms << "ms";
  115.   std::cout << " (" << total_time_ms/1000 << "seconds or " << total_time_ms/(1000*60) << " minutes)" << std::endl; 
  116.    return 0;
  117. }
Success #stdin #stdout 14.13s 159232KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 

********** Times in microseconds (us) **********
Elements SORT(List, Vector)
elements	, list_time	, vector_time
10		, 3, (150%),		2 , (100%)
1000		, 141, (238%),		59 , (100%)
10000		, 1658, (261%),		633 , (100%)
100000		, 25487, (327%),		7792 , (100%)
1000000		, 492468, (529%),		92956 , (100%)
10000000		, 8982242, (826%),		1087295 , (100%)
Exiting test,. the whole measuring took 14164ms (14seconds or 0 minutes)
https://ideone.com/3eouT
language:
C++14 (gcc 8.3)
created:
11 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!