fork download
  1. //
  2. // kjellkod.wordpress.com
  3. // Comparison of sort. std::vector vs std::list
  4. //
  5.  
  6. #include <list>
  7. #include <vector>
  8. #include <iostream>
  9. #include <functional>
  10. #include <random>>
  11. #include <iostream>
  12. #include <chrono>
  13. #include <string>
  14. #include <numeric>
  15. #include <algorithm>
  16.  
  17. namespace g2
  18. {
  19. typedef std::chrono::high_resolution_clock clock;
  20. typedef std::chrono::microseconds microseconds;
  21. typedef std::chrono::milliseconds milliseconds;
  22.  
  23. clock::time_point now(){return clock::now();}
  24.  
  25. microseconds intervalUs(const clock::time_point& t1, const clock::time_point& t0)
  26. {return std::chrono::duration_cast<microseconds>(t1 - t0);}
  27.  
  28. milliseconds intervalMs(const clock::time_point& t1,const clock::time_point& t0)
  29. {return std::chrono::duration_cast<milliseconds>(t1 - t0);}
  30.  
  31.  
  32. class StopWatch
  33. {
  34. clock::time_point start_;
  35. public:
  36. StopWatch() : start_(clock::now()){}
  37. clock::time_point restart() { start_ = clock::now(); return start_;}
  38. microseconds elapsedUs() { return intervalUs(now(), start_);}
  39. milliseconds elapsedMs() {return intervalMs(now(), start_);}
  40. };
  41. } // g2
  42.  
  43.  
  44.  
  45.  
  46.  
  47. typedef unsigned int Number;
  48. typedef std::list<Number> NumbersInList;
  49. typedef std::vector<Number> NumbersInVector;
  50. typedef long long int TimeValue;
  51.  
  52.  
  53. // Used for debugging and verification,
  54. // normally disabled
  55. template<typename Container>
  56. void printValues(const std::string& msg, const Container& values)
  57. {
  58. std::cout << msg << std::endl;
  59. std::for_each(values.begin(), values.end(),
  60. [&](const Number& n) { std::cout << " " << n << " "; });
  61.  
  62. std::cout << "\n" << std::endl;
  63. }
  64.  
  65.  
  66.  
  67.  
  68. void listVsVectorSort(size_t nbr_of_randoms)
  69. {
  70. std::uniform_int_distribution<int> distribution(0, nbr_of_randoms);
  71. std::mt19937 engine((unsigned int)time(0)); // Mersenne twister MT19937
  72. auto generator = std::bind(distribution, engine);
  73. NumbersInVector vector(nbr_of_randoms);
  74. NumbersInList list;
  75.  
  76. std::for_each(vector.begin(), vector.end(), [&](Number& n) { n = generator(); list.push_back(n); } );
  77. TimeValue list_time;
  78. { // list measure sort
  79. g2::StopWatch watch;
  80. list.sort();
  81. list_time = watch.elapsedUs().count();
  82. }
  83. TimeValue vector_time;
  84. { // vector measure sort
  85. g2::StopWatch watch;
  86. std::sort(vector.begin(), vector.end());
  87. vector_time = watch.elapsedUs().count();
  88. }
  89.  
  90. std::cout << nbr_of_randoms << "\t\t, " << list_time << "\t\t, " << 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. listVsVectorSort(10);
  106. listVsVectorSort(100);
  107. listVsVectorSort(1000);
  108. listVsVectorSort(10000);
  109. listVsVectorSort(20000);
  110. listVsVectorSort(30000);
  111. listVsVectorSort(40000);
  112. size_t cnt = 50000;
  113. do{
  114. listVsVectorSort(cnt);
  115. cnt+=50000;
  116. }
  117. while(cnt <= 1000000);
  118. listVsVectorSort(1000000);
  119.  
  120.  
  121. auto total_time_ms = watch.elapsedMs().count();
  122. std::cout << "Exiting test,. the whole measuring took " << total_time_ms << "ms";
  123. std::cout << " (" << total_time_ms/1000 << "seconds or " << total_time_ms/(1000*60) << " minutes)" << std::endl;
  124. return 0;
  125. }
Success #stdin #stdout 10.64s 3032KB
stdin
Standard input is empty
stdout

********** Times in microseconds (us) **********
Elements SORT(List, Vector)
elements	, list_time	, vector_time
10		, 3		, 2
100		, 11		, 9
1000		, 134		, 51
10000		, 1561		, 604
20000		, 3617		, 1334
30000		, 5305		, 2014
40000		, 7553		, 2666
50000		, 10680		, 3473
100000		, 23594		, 7295
150000		, 40542		, 11440
200000		, 56559		, 15667
250000		, 78068		, 19724
300000		, 113920		, 23863
350000		, 125641		, 28211
400000		, 145099		, 33051
450000		, 161807		, 37576
500000		, 192667		, 41732
550000		, 251834		, 46071
600000		, 274409		, 51250
650000		, 278399		, 55559
700000		, 309250		, 60115
750000		, 325837		, 65044
800000		, 367590		, 69802
850000		, 379411		, 74055
900000		, 417667		, 78844
950000		, 433513		, 83645
1000000		, 478211		, 87523
1000000		, 459456		, 88269
Exiting test,. the whole measuring took 10670ms (10seconds or 0 minutes)