language: C++11 (gcc-4.7.2)
date: 400 days 15 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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191

//
// compare linear insert with different POD sizes. std::list vs std::vector
//
 
#include <list>
#include <vector>
#include <deque>
#include <iostream>
#include <iomanip>
#include <random>
#include <functional>
#include <iostream>
#include <chrono>
#include <string>
#include <numeric>
#include <algorithm>
#include <cassert>
 
 
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 long long int            TimeValue;
const std::string rows_explained = "elements         list_time   vector_time   deque_time ";
 
 
// Silly POD to test with variadic POD size
template<Number Size>
struct POD
{
   Number a[Size];
 
  bool operator>=(const POD& b) const
  {
    return (this->a[0] >= b.a[0]);
  }
};
 
 
// Random integer function from http://www2.research.att.com/~bs/C++0xFAQ.html#std-random
int random_int(int low, int high)
{
  using namespace std;
  static default_random_engine engine {};
  typedef uniform_int_distribution<int> Distribution;
  static Distribution distribution {};
  return distribution(engine, Distribution::param_type{low, high});
}
 
 
 
// Use a template approach to use functor, function pointer or lambda to insert an
// element in the input container and return the "time result".
// Search is LINEAR. Elements are insert in SORTED order
template<typename ValueType, typename Container>
void linearInsertion(const std::vector<ValueType>& numbers, Container& container)
{
    std::for_each(numbers.begin(), numbers.end(),
                  [&](const ValueType& n)
    {
        auto itr = container.begin();
        for (; itr!= container.end(); ++itr)
        {
            if ((*itr) >= n) {
                break;
            }
        }
        container.insert(itr, n);
    });
}
 
// Measure time in microseconds (us) for linear insert in a std container
template<typename Container, typename ValueType>
TimeValue linearInsertPerformance(const std::vector<ValueType>& randoms, Container& container)
{
    g2::StopWatch watch;
    linearInsertion<ValueType, Container>(std::cref(randoms), container);
    auto time = watch.elapsedUs().count();
    return time;
}
 
template<Number SizeOfPod>
void listVsVectorLinearPerformance(const size_t nbr_of_randoms)
{
  // Generate n random values and push to storage
  typedef POD<SizeOfPod> POD_value;
  std::vector<POD_value> values(nbr_of_randoms);
  const auto lower_limit = 0;
  const auto upper_limit = nbr_of_randoms -1;
  std::for_each(values.begin(), values.end(), [&](POD_value& n) { n.a[0] = random_int(lower_limit, upper_limit);});
 
  TimeValue list_time;
  TimeValue vector_time;
  TimeValue deque_time;
  std::cout << nbr_of_randoms << ",\t" << std::flush;
  { // force local scope - to clear up the containers at exit
    std::list<POD_value>      list;
    list_time = linearInsertPerformance<std::list<POD_value>, POD_value>(values, list);
  }
  {
    std::vector<POD_value>    vector;
    vector_time = linearInsertPerformance<std::vector<POD_value>, POD_value>(values, vector);
  }
 
  {
    std::deque<POD_value>    deque;
    deque_time = linearInsertPerformance<std::deque<POD_value>, POD_value>(values, deque);
  }
 
 
  std::cout << "\t" << list_time << ",\t" << vector_time << ",\t" << deque_time;
  std::cout << ",\tsizeof(POD): " << sizeof(POD_value) << " bytes" << std::endl << std::flush;
 
}
 
   template<Number PodSizeIn4ByteIncrements>
   void measure()
   {
     g2::StopWatch watch;
     std::cout << "Measuring In Microseconds (us)" << std::endl;
     std::cout << rows_explained << std::endl;
 
     // small increments for measuring up to 4000
     listVsVectorLinearPerformance<PodSizeIn4ByteIncrements>(100);
     listVsVectorLinearPerformance<PodSizeIn4ByteIncrements>(200);
     listVsVectorLinearPerformance<PodSizeIn4ByteIncrements>(400);
     listVsVectorLinearPerformance<PodSizeIn4ByteIncrements>(800);
     listVsVectorLinearPerformance<PodSizeIn4ByteIncrements>(1000);
     listVsVectorLinearPerformance<PodSizeIn4ByteIncrements>(2000);
     listVsVectorLinearPerformance<PodSizeIn4ByteIncrements>(3000);
     listVsVectorLinearPerformance<PodSizeIn4ByteIncrements>(4000);
     listVsVectorLinearPerformance<PodSizeIn4ByteIncrements>(5000);
 
     for(auto cnt = 5000; cnt <= 11000; cnt+=2000)
     {
       listVsVectorLinearPerformance<PodSizeIn4ByteIncrements>(cnt);
     }
     auto total_time_ms = watch.elapsedMs().count();
     std::cout << "[" << rows_explained << "]" << std::endl;
 
     typedef POD<PodSizeIn4ByteIncrements> POD_value;
     std::cout << "Test finished for " << sizeof(POD_value) << " bytes POD" << std::endl;
     std::cout << "The POD sized test took " << total_time_ms << " milliseconds (or " << total_time_ms/1000 << " seconds)\n\n" << std::endl;
   }
 
 
 
   int main(int argc, char** argv)
   {
     g2::StopWatch watch;
     measure<1>(); // measure 4 bytes
     measure<2>(); // measure 8 bytes
     measure<4>(); // measure 16 bytes
     measure<8>(); // 32 bytes
     measure<16>(); // 64 bytes
     measure<32>(); // 128 bytes*/
     measure<64>(); // 256 bytes
     auto total_time_s = watch.elapsedMs().count()/1000;
     std::cout << "\n\n**********************************************\n" << std::endl;
     std::cout << "Exiting test: the whole measuring took " << total_time_s << " seconds";
     std::cout << " (or " << total_time_s/(60) << " minutes)" << std::endl;
 
     return 0;
   }
 
 
 
  • upload with new input
  • # 1:   hide   clone   input   400 days 15 hours ago

    result: Time limit exceeded     time: 15s    memory: 5312 kB     signal: 24 (SIGXCPU) 

    Measuring In Microseconds (us)
elements         list_time   vector_time   deque_time 
100,		18,	18,	21,	sizeof(POD): 4 bytes
200,		30,	31,	46,	sizeof(POD): 4 bytes
400,		83,	83,	136,	sizeof(POD): 4 bytes
800,		290,	275,	449,	sizeof(POD): 4 bytes
1000,		403,	393,	685,	sizeof(POD): 4 bytes
2000,		1497,	1470,	2573,	sizeof(POD): 4 bytes
3000,		3235,	3179,	5536,	sizeof(POD): 4 bytes
4000,		5637,	5542,	9633,	sizeof(POD): 4 bytes
5000,		10446,	8625,	15253,	sizeof(POD): 4 bytes
5000,		10594,	8662,	15306,	sizeof(POD): 4 bytes
7000,		33073,	16752,	29667,	sizeof(POD): 4 bytes
9000,		71371,	27394,	48053,	sizeof(POD): 4 bytes
11000,		127991,	40922,	72330,	sizeof(POD): 4 bytes
[elements         list_time   vector_time   deque_time ]
Test finished for 4 bytes POD
The POD sized test took 582 milliseconds (or 0 seconds)


Measuring In Microseconds (us)
elements         list_time   vector_time   deque_time 
100,		16,	15,	22,	sizeof(POD): 8 bytes
200,		29,	37,	54,	sizeof(POD): 8 bytes
400,		80,	115,	167,	sizeof(POD): 8 bytes
800,		262,	419,	600,	sizeof(POD): 8 bytes
1000,		413,	617,	935,	sizeof(POD): 8 bytes
2000,		1512,	2355,	3611,	sizeof(POD): 8 bytes
3000,		3548,	5511,	7926,	sizeof(POD): 8 bytes
4000,		9322,	9041,	13632,	sizeof(POD): 8 bytes
5000,		19051,	14150,	21541,	sizeof(POD): 8 bytes
5000,		19035,	14174,	21401,	sizeof(POD): 8 bytes
7000,		50541,	27541,	41525,	sizeof(POD): 8 bytes
9000,		98414,	45873,	68926,	sizeof(POD): 8 bytes
11000,		165153,	70999,	103739,	sizeof(POD): 8 bytes
[elements         list_time   vector_time   deque_time ]
Test finished for 8 bytes POD
The POD sized test took 847 milliseconds (or 0 seconds)


Measuring In Microseconds (us)
elements         list_time   vector_time   deque_time 
100,		13,	19,	32,	sizeof(POD): 16 bytes
200,		30,	48,	66,	sizeof(POD): 16 bytes
400,		97,	137,	203,	sizeof(POD): 16 bytes
800,		278,	484,	742,	sizeof(POD): 16 bytes
1000,		405,	743,	1117,	sizeof(POD): 16 bytes
2000,		1549,	2806,	4296,	sizeof(POD): 16 bytes
3000,		5326,	6231,	9918,	sizeof(POD): 16 bytes
4000,		13891,	11109,	18281,	sizeof(POD): 16 bytes
5000,		27564,	17827,	30167,	sizeof(POD): 16 bytes
5000,		28079,	18142,	29430,	sizeof(POD): 16 bytes
7000,		69680,	39270,	61577,	sizeof(POD): 16 bytes
9000,		133828,	70351,	109575,	sizeof(POD): 16 bytes
11000,		217309,	112564,	167331,	sizeof(POD): 16 bytes
[elements         list_time   vector_time   deque_time ]
Test finished for 16 bytes POD
The POD sized test took 1215 milliseconds (or 1 seconds)


Measuring In Microseconds (us)
elements         list_time   vector_time   deque_time 
100,		17,	25,	31,	sizeof(POD): 32 bytes
200,		30,	65,	83,	sizeof(POD): 32 bytes
400,		88,	207,	303,	sizeof(POD): 32 bytes
800,		285,	760,	1084,	sizeof(POD): 32 bytes
1000,		417,	1185,	1669,	sizeof(POD): 32 bytes
2000,		2449,	4630,	6661,	sizeof(POD): 32 bytes
3000,		8737,	12297,	16092,	sizeof(POD): 32 bytes
4000,		19623,	26994,	29460,	sizeof(POD): 32 bytes
5000,		34135,	44987,	47772,	sizeof(POD): 32 bytes
5000,		35326,	53879,	49129,	sizeof(POD): 32 bytes
7000,		80189,	101926,	100646,	sizeof(POD): 32 bytes
9000,		148011,	172254,	170403,	sizeof(POD): 32 bytes
11000,		238875,	265761,	254506,	sizeof(POD): 32 bytes
[elements         list_time   vector_time   deque_time ]
Test finished for 32 bytes POD
The POD sized test took 1936 milliseconds (or 1 seconds)


Measuring In Microseconds (us)
elements         list_time   vector_time   deque_time 
100,		14,	33,	53,	sizeof(POD): 64 bytes
200,		36,	96,	138,	sizeof(POD): 64 bytes
400,		107,	361,	491,	sizeof(POD): 64 bytes
800,		371,	1714,	1882,	sizeof(POD): 64 bytes
1000,		652,	2903,	2882,	sizeof(POD): 64 bytes
2000,		5208,	14625,	13156,	sizeof(POD): 64 bytes
3000,		13885,	36723,	34668,	sizeof(POD): 64 bytes
4000,		29540,	66297,	59874,	sizeof(POD): 64 bytes
5000,		48984,	106224,	97407,	sizeof(POD): 64 bytes
5000,		48851,	106039,	102512,	sizeof(POD): 64 bytes
7000,		98475,	209986,	212567,	sizeof(POD): 64 bytes
9000,		208395,	359029,	347251,	sizeof(POD): 64 bytes
11000,		308337,	561461,	540677,	sizeof(POD): 64 bytes
[elements         list_time   vector_time   deque_time ]
Test finished for 64 bytes POD
The POD sized test took 3651 milliseconds (or 3 seconds)


Measuring In Microseconds (us)
elements         list_time   vector_time   deque_time 
100,		20,	55,	67,	sizeof(POD): 128 bytes
200,		34,	184,	243,	sizeof(POD): 128 bytes
400,		99,	664,	825,	sizeof(POD): 128 bytes
800,		344,	3223,	3373,	sizeof(POD): 128 bytes
1000,		603,	5543,	5436,	sizeof(POD): 128 bytes
2000,		5131,	26725,	22801,	sizeof(POD): 128 bytes
3000,		15589,	62033,	54406,	sizeof(POD): 128 bytes
4000,		29407,	114862,	105530,	sizeof(POD): 128 bytes
5000,		54591,	186082,	167228,	sizeof(POD): 128 bytes
5000,		49293,	188096,	168613,	sizeof(POD): 128 bytes
7000,		116838,	388462,	334585,	sizeof(POD): 128 bytes
9000,		196422,	664962,	582932,	sizeof(POD): 128 bytes
11000,		329338,	1041045,	890064,	sizeof(POD): 128 bytes
[elements         list_time   vector_time   deque_time ]
Test finished for 128 bytes POD
The POD sized test took 5829 milliseconds (or 5 seconds)


Measuring In Microseconds (us)
elements         list_time   vector_time   deque_time 
100,		22,	114,	111,	sizeof(POD): 256 bytes
200,		48,	389,	437,	sizeof(POD): 256 bytes
400,		166,	1703,	1636,	sizeof(POD): 256 bytes
800,		666,	7938,	6714,	sizeof(POD): 256 bytes
1000,		990,	12154,	11316,	sizeof(POD): 256 bytes
2000,		6986,	52560,	51073,	sizeof(POD): 256 bytes
3000,		17463,	130203,	118161,	sizeof(POD): 256 bytes
4000,		35687,	239496,	208851,	sizeof(POD): 256 bytes
5000,
TESTING: POD (growing) 15s list vs vector. linear search