language: C++11 (gcc-4.7.2)
date: 396 days 16 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
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266

// kjellkod.wordpress.com
// Silly example of 
// Vector vs LinkedList. Random element and linear traversal to 
// get to the right position. Insertion gives sorted order.
//
// OBSERVE: please turn on OPTIMIZATION when running this code on your own computer, i.e. something like
//         g++ -std=c++11 -O3
 
 
#include <list>
#include <vector>
#include <iostream>
#include <iomanip>
#include <functional>
#include <random>
#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 std::list<Number>           NumbersInList;
typedef std::vector<Number>         NumbersInVector;
typedef long long int               TimeValue;
 
 
/*   // Lambda expression for generating a random number using the 'mersenne twister distribution'
     // http://en.wikipedia.org/wiki/Mersenne_twister
auto random_int = [&](const Number& low, const Number& high) -> Number {
    std::uniform_int_distribution<int> distribution(low, high);
    std::mt19937 engine((unsigned int)time(0)); // Mersenne twister MT19937
    auto generator = std::bind(distribution, engine);
    return generator();
};   */
 
// 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});
}
 
// test printout just to see the distribution
void print_distribution(std::vector<Number>& values)
{  
  for (int i = 0; i<values.size(); ++i) 
  {
    std::cout << i << '\t';
    for (int j=0; j<values[i]; ++j) std::cout << '*';
    std::cout << '\n';
  }
}
 
 
 
 
// 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 Container>
void linearInsertion(const NumbersInVector& numbers, Container& container)
{
    std::for_each(numbers.begin(), numbers.end(),
                  [&](const Number& n)
    {
        auto itr = container.begin();
        for (; itr!= container.end(); ++itr)
        {
            if ((*itr) >= n) {
                break;
            }
        }
        container.insert(itr, n);
    });
}
 
// Measure time in milliseconds for linear insert in a std container
template<typename Container>
TimeValue linearInsertPerformance(const NumbersInVector& randoms, Container& container)
{
    g2::StopWatch watch;
    linearInsertion(std::cref(randoms), container);
    auto time = watch.elapsedUs().count();
    return time;
}
 
 
 
// Delete of an element from a std container. The Delete of an item is from a random position.
template<typename Container>
void linearErase(Container& container)
{
    // Possibly O(n) to get initially but we use it for the random number generation
    //    and it is only done ONCE
    auto size = container.size();
    while (false == container.empty())
    {
        // force silly linear search to the right position to do a delete
        Number random_position = random_int(0, size -1);
        auto itr = container.begin();
 
        // using hand-wrought 'find' to force linear search to the position
        for (unsigned int idx = 0; idx != random_position; ++idx)
        {
            ++itr; // silly linear
        }
        container.erase(itr);
        --size;
    }
}
 
// Measure time in milliseconds for linear remove (i.e. "erase") in a std container
template<typename Container>
TimeValue linearRemovePerformance(Container& container)
{
    g2::StopWatch watch;
    linearErase(container);
    auto time = watch.elapsedUs().count();
    return time;
}
 
 
void listVsVectorLinearPerformance(size_t nbr_of_randoms)
{
  // Generate n random values and push to storage
  NumbersInVector     values(nbr_of_randoms);
  std::for_each(values.begin(), values.end(), [&](Number& n) { n = random_int(0, nbr_of_randoms -1);}); 
  //print_distribution(values); 
 
  TimeValue list_time;
  TimeValue list_delete_time;
  TimeValue vector_time;    
  TimeValue vector_delete_time;
  std::cout << nbr_of_randoms << ",\t" << std::flush;
 
 
  { // force local scope - to clear up the containers at exit   
    NumbersInList      list;
    list_time = linearInsertPerformance(values, list);
    list_delete_time = linearRemovePerformance(list);
  }
  {
    NumbersInVector    vector;
    vector_time = linearInsertPerformance(values, vector);
    std::cout << " "  << ", ";
    vector_delete_time = linearRemovePerformance(vector);
  }
  std::cout <<  list_time << ", " << vector_time << ",";
  std::cout << "\t\t" << list_delete_time << ", " << vector_delete_time << std::endl << std::flush;
}
 
 
 
 
// 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;
}
 
 
 
// disabled normally,. only used to verify during dev,time not test,time
template<typename ProspectLinear>
void verifyLinearSort(const NumbersInVector& valid_container, const ProspectLinear& container)
{
  auto toCheckItr = container.begin();
  std::for_each(valid_container.begin(), valid_container.end(),
    [&](const Number& n)
  {
    assert(toCheckItr != container.end());
    Number n2 = (*toCheckItr);
    if(n != n2)
    {
      printValues("\nTrue Linear should be: ", valid_container);
      printValues("\nError in comparison printing numbers: ", container);
      std::cout << "check error: " << n << "vs value: " << n2 << std::endl;
      assert(n == n2 && "not matching numbers");
    }
    ++toCheckItr;
  });
}
 
 
 
int main(int argc, char** argv)
{ 
 
  // Generate N random integers and insert them in its proper position in the numerical order using
  // LINEAR search
  std::cout << "Comparison of insert and erase (delete) of item from a linked list and vector (array)" << std::endl;
  std::cout << "Insert is done on random item, with linear search to get to the insert position" << std::endl;
  std::cout << "Erase is done on a random position within the available elements. Linear search to get to the position" << std::endl;
  std::cout << "\n\n Linked-list shows close to exponential time usage in contrast to the vectors almost linear time usage"<< std::endl;
  std::cout << "The HUGE difference is due to that a vector is sequential in memory and thereby is maximazing cache-line usage" << std::endl;
 std::cout << "The linked-list uses RAM much more and cache-line misses are maximized. " << std::endl;
 std::cout << "\n\n CONCLUSION: When comparing linked list and vector/array then the linear search COMPLETELY" << std::endl; 
 std::cout << "DOMINATES the time consumption. Cache-line friendly data structures show much promise in speed" << std::endl;
 std::cout << "The fact that a vector uses many memory shuffling when increasing, inserting deleting elements is of " << std::endl; 
std::cout << "LIMITED importance compared to the RAM access slow-down for a linked-list" << std::endl;
 
std::cout << "\nFor test results on Windows and Linux please go to: " << std::endl;
std::cout << "https://docs.google.com/spreadsheet/pub?key=0AkliMT3ZybjAdGJMU1g5Q0QxWEluWGRzRnZKZjNMMGc&output=html" << std::endl;
 
std::cout << "\n\n********** Times in microseconds**********" << std::endl;
std::cout << "Elements ADD (List, Vector)\tERASE(List, Vector)" << std::endl;
//[elements, linear add time [ms] [list, vector],    linear erase time[ms] [list, vector]" << std::endl;
 
  g2::StopWatch watch;
  listVsVectorLinearPerformance(100);
  listVsVectorLinearPerformance(200);
  listVsVectorLinearPerformance(500);
  listVsVectorLinearPerformance(1000);
  listVsVectorLinearPerformance(4000);
  listVsVectorLinearPerformance(10000);
  listVsVectorLinearPerformance(20000);
  listVsVectorLinearPerformance(40000);
  auto total_time_ms = watch.elapsedMs().count();
 
  std::cout << "Exiting test,. the whole measuring took " << total_time_ms << " milliseconds";
  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   396 days 16 hours ago

    result: Success     time: 9.77s    memory: 3124 kB     returned value: 0 

    Comparison of insert and erase (delete) of item from a linked list and vector (array)
Insert is done on random item, with linear search to get to the insert position
Erase is done on a random position within the available elements. Linear search to get to the position


 Linked-list shows close to exponential time usage in contrast to the vectors almost linear time usage
The HUGE difference is due to that a vector is sequential in memory and thereby is maximazing cache-line usage
The linked-list uses RAM much more and cache-line misses are maximized. 


 CONCLUSION: When comparing linked list and vector/array then the linear search COMPLETELY
DOMINATES the time consumption. Cache-line friendly data structures show much promise in speed
The fact that a vector uses many memory shuffling when increasing, inserting deleting elements is of 
LIMITED importance compared to the RAM access slow-down for a linked-list

For test results on Windows and Linux please go to: 
https://docs.google.com/spreadsheet/pub?key=0AkliMT3ZybjAdGJMU1g5Q0QxWEluWGRzRnZKZjNMMGc&output=html


********** Times in microseconds**********
Elements ADD (List, Vector)	ERASE(List, Vector)
100,	 , 16, 15,		22, 9
200,	 , 33, 35,		33, 19
500,	 , 134, 153,		131, 66
1000,	 , 550, 513,		451, 185
4000,	 , 6809, 7318,		5900, 2081
10000,	 , 100421, 44943,		110069, 11790
20000,	 , 589209, 182490,		606982, 46515
40000,	 , 3430062, 797146,		3638707, 250067
Exiting test,. the whole measuring took 9837 milliseconds (9seconds or 0 minutes)