Join the contest
language: C++0x (gcc-4.5.1)
date: 210 days 14 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

/* SMART Linked-list vs "normal" linked-list vs Vector. 15seconds maximum run-time 
Linear search and sorted insertion. std::list remembers last position to 
minimize overhead in traversing the list.*/
 
#include <list>
#include <vector>
#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 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});
}
 
 
 
 
 
 
// 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);
    });
}
 
namespace{
// A little bit smarter --- remembers the last insertion point's position and can 
// start from that if wanted-position is >= last-position: this is calculated from the values
// and not from the absolute positions
TimeValue linearSmartInsertPerformance(const NumbersInVector& numbers, NumbersInList& container)
{
    g2::StopWatch watch; 
    auto last_inserted_value = 0;
    auto last_iter_position = container.begin();
 
    std::for_each(numbers.begin(), numbers.end(),
                  [&](const Number& n)
    {
        auto itr = container.begin();
        if(n >= last_inserted_value)
        {
           itr = last_iter_position;
        }
           
        for (; itr!= container.end(); ++itr)
        {
            if ((*itr) >= n) {
                break;
            }
        }
        last_iter_position = container.insert(itr, n);
        last_inserted_value = n;
    });
    auto time = watch.elapsedUs().count();
    return time;
}
} // anonymous namespace
 
// 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;
}
 
 
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 smarter_list_time;
  TimeValue list_time;
  TimeValue vector_time;    
  std::cout << nbr_of_randoms << ",\t" << std::flush;
 
 
  { // force local scope - to clear up the containers at exit   
    NumbersInList      list;
    smarter_list_time = linearSmartInsertPerformance(values, list);
  }
  {
    NumbersInList      list;
    list_time = linearInsertPerformance(values, list);
  }
  {
    NumbersInVector    vector;
    vector_time = linearInsertPerformance(values, vector);
    std::cout << " "  << ", ";
  }
  std::cout <<  smarter_list_time << ", " << list_time << ", " << vector_time << std::endl << std::flush;
}
 
 
int main(int argc, char** argv)
{
 
std::cout << "\n\n********** Times in microseconds**********" << std::endl;
std::cout << "Elements ADD (Smarter-List,   List,    Vector)" << std::endl;
 
  g2::StopWatch watch; // only 15seconds available, therefore the short ranges
  listVsVectorLinearPerformance(10);
  listVsVectorLinearPerformance(100);
  listVsVectorLinearPerformance(500);
  listVsVectorLinearPerformance(1000);
  listVsVectorLinearPerformance(2000);
  listVsVectorLinearPerformance(3000);
  listVsVectorLinearPerformance(4000);
  listVsVectorLinearPerformance(6000);
  listVsVectorLinearPerformance(8000);
  listVsVectorLinearPerformance(16000);
  listVsVectorLinearPerformance(32000);
  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
  • # 3:   show   clone   input   45 days 15 hours ago    Time limit exceeded
  • # 2:   show   clone   input   206 days 18 hours ago    Time limit exceeded
  • # 1:   hide   clone   input   210 days 14 hours ago

    result: Success     time: 5.01s    memory: 3088 kB     returned value: 0 

    
********** Times in microseconds**********
Elements ADD (Smarter-List,   List,    Vector)
10,	 , 3, 1, 3
100,	 , 11, 11, 13
500,	 , 115, 140, 141
1000,	 , 380, 501, 514
2000,	 , 1343, 1876, 1888
3000,	 , 2998, 4385, 4156
4000,	 , 5067, 7390, 7260
6000,	 , 15504, 33669, 16221
8000,	 , 37144, 76678, 28733
16000,	 , 229060, 425824, 114170
32000,	 , 1267700, 2246701, 498444
Exiting test,. the whole measuring took 5037 milliseconds (5seconds or 0 minutes)
SMART Linked-list vs NORMAL linked-list vs VECTOR. 15s list vs vector. Linear search and sorted insertion. std::list remembers last position to minimize overhead in traversing the list.