language: C++11 (gcc-4.7.2)
date: 289 days 22 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

/* Hack of earlier code to compare vectors worst-case towards linked-list best case
I.e. 1) insertion of x elements at first position
     1b) The same but do for vector at last position
*/
 
#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;
 
 
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));
}
template<typename Container>
void firstPositionInsertion(const NumbersInVector& numbers, Container& container)
{
    std::for_each(numbers.begin(), numbers.end(),
                  [&](const Number& n)
    {
        auto itr = container.begin();
        container.insert(itr, n);
    });
}
 
// For vector, push always at back position
TimeValue lastPositionInsertionPerformance(const NumbersInVector& numbers, 
                                            NumbersInVector& vector)
{
    g2::StopWatch watch;
    std::for_each(numbers.begin(), numbers.end(),
                  [&](const Number& n)
    {
            vector.push_back(n);
    });
 
        auto time = watch.elapsedUs().count();
    return time;
}
 
 
// Measure time in milliseconds for linear insert in a std container
template<typename Container>
TimeValue linearInsertPerformance(const NumbersInVector& randoms, Container& container)
{
    g2::StopWatch watch;
    firstPositionInsertion(std::cref(randoms), container);
    auto time = watch.elapsedUs().count();
    return time;
}
 
 
 
void addPerformance(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);}); 
 
  NumbersInVector vector_worst;
  NumbersInVector vector_best;
  NumbersInList   list;
  
      
  std::cout << nbr_of_randoms << ",  " << std::flush;
  TimeValue list_time = linearInsertPerformance(values, list);
  TimeValue vector_best_time = lastPositionInsertionPerformance(values, vector_best);
  TimeValue vector_worst_time = linearInsertPerformance(values, vector_worst);
  std::cout << list_time << ", " << vector_best_time << ", " << vector_worst_time << " " << std::endl << std::flush;
}
 
 
 
 
 
 
int main(int argc, char** argv)
{ 
 
  std::cout << "Perhaps the most common 'data collecting' operation is putting 'one piece of data" << std::endl;
  std::cout << "  in front of an older piece of data and so forth.\n" << std::endl; 
  std::cout << "For linked-list this is insertion at index 0\n" << std::endl;
  std::cout << "For std::vector  the 'push at front' operation is working against nature of the " << std::endl;
  std::cout  << "  data structure and in this common scenario such use is called 'naive'\n" << std::endl;
  std::cout << "For std::vector it is natural in this scenario to work in the direction of 'growth' " << std::endl; 
  std::cout << "i.e. push_back. It solves the same task but works as intended with the nature of the " << std::endl; 
  std::cout << "  data structure.\n\n" << std::endl; 
 
  std::cout << "elements, list, vector_best, vector_worst(naive)" << std::endl;
  g2::StopWatch watch;
  addPerformance(10);
  addPerformance(100);
  addPerformance(500);
  addPerformance(1000);
  addPerformance(2000);
  addPerformance(10000);
  addPerformance(20000);
  addPerformance(40000);
  addPerformance(100000);
  // more than this will timeout on ideone
   // addPerformance(500000);
  //addPerformance(1000000);
 
  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   289 days 22 hours ago

    result: Success     time: 4.2s    memory: 3068 kB     returned value: 0 

    Perhaps the most common 'data collecting' operation is putting 'one piece of data
  in front of an older piece of data and so forth.

For linked-list this is insertion at index 0

For std::vector  the 'push at front' operation is working against nature of the 
  data structure and in this common scenario such use is called 'naive'

For std::vector it is natural in this scenario to work in the direction of 'growth' 
i.e. push_back. It solves the same task but works as intended with the nature of the 
  data structure.


elements, list, vector_best, vector_worst(naive)
10,  3, 6, 1 
100,  7, 3, 13 
500,  43, 7, 83 
1000,  70, 10, 285 
2000,  149, 27, 986 
10000,  928, 159, 22613 
20000,  1578, 284, 97330 
40000,  3138, 582, 553636 
100000,  7802, 1179, 3555756 
Exiting test,. the whole measuring took 4266 milliseconds (4seconds or 0 minutes)