language: C++11 (gcc-4.7.2)
date: 73 days 5 hours ago
link:
visibility: public 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125

//
//   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;
}
  • upload with new input
  • # 1:   hide   clone   input   73 days 5 hours ago

    result: Success     time: 10.64s    memory: 3032 kB     returned value: 0 

    
********** 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)
15s list vs vector
SORT using std::sort (vector) and std::list::sort