// // kjellkod.wordpress.com // Comparison of sort. std::vector vs std::list // #include <list> #include <vector> #include <iostream> #include <functional> #include <random>> #include <iostream> #include <chrono> #include <string> #include <numeric> #include <algorithm> namespace g2 { typedef std::chrono::high_resolution_clock clock; typedef std::chrono::microseconds microseconds; typedef std::chrono::milliseconds milliseconds; clock::time_point now(){return clock::now();} microseconds intervalUs(const clock::time_point& t1, const clock::time_point& t0) {return std::chrono::duration_cast<microseconds>(t1 - t0);} milliseconds intervalMs(const clock::time_point& t1,const clock::time_point& t0) {return std::chrono::duration_cast<milliseconds>(t1 - t0);} class StopWatch { clock::time_point start_; public: StopWatch() : start_(clock::now()){} clock::time_point restart() { start_ = clock::now(); return start_;} microseconds elapsedUs() { return intervalUs(now(), start_);} milliseconds elapsedMs() {return intervalMs(now(), start_);} }; } // g2 typedef unsigned int Number; typedef std::list<Number> NumbersInList; typedef std::vector<Number> NumbersInVector; typedef long long int TimeValue; // Used for debugging and verification, // normally disabled template<typename Container> void printValues(const std::string& msg, const Container& values) { std::cout << msg << std::endl; std::for_each(values.begin(), values.end(), [&](const Number& n) { std::cout << " " << n << " "; }); std::cout << "\n" << std::endl; } void listVsVectorSort(size_t nbr_of_randoms) { std::uniform_int_distribution<int> distribution(0, nbr_of_randoms); std::mt19937 engine((unsigned int)time(0)); // Mersenne twister MT19937 auto generator = std::bind(distribution, engine); NumbersInVector vector(nbr_of_randoms); NumbersInList list; std::for_each(vector.begin(), vector.end(), [&](Number& n) { n = generator(); list.push_back(n); } ); TimeValue list_time; { // list measure sort g2::StopWatch watch; list.sort(); list_time = watch.elapsedUs().count(); } TimeValue vector_time; { // vector measure sort g2::StopWatch watch; std::sort(vector.begin(), vector.end()); vector_time = watch.elapsedUs().count(); } std::cout << nbr_of_randoms << "\t\t, " << list_time << "\t\t, " << vector_time << std::endl; } int main(int argc, char** argv) { std::cout << "\n\n********** Times in microseconds (us) **********" << std::endl; std::cout << "Elements SORT(List, Vector)" << std::endl; std::cout << "elements\t, list_time\t, vector_time" << std::endl; g2::StopWatch watch; listVsVectorSort(10); listVsVectorSort(100); listVsVectorSort(1000); listVsVectorSort(10000); listVsVectorSort(20000); listVsVectorSort(30000); listVsVectorSort(40000); size_t cnt = 50000; do{ listVsVectorSort(cnt); cnt+=50000; } while(cnt <= 1000000); listVsVectorSort(1000000); auto total_time_ms = watch.elapsedMs().count(); std::cout << "Exiting test,. the whole measuring took " << total_time_ms << "ms"; std::cout << " (" << total_time_ms/1000 << "seconds or " << total_time_ms/(1000*60) << " minutes)" << std::endl; return 0; }
Standard input is empty
********** 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)