/* 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>
#include <string.h>
template < class T> struct fastListElement
{
public:
T value;
fastListElement<T>* next;
};
template < class T> class fastListIterator
{
public:
fastListIterator(fastListElement<T>* init, fastListElement<T>* ibefore): current(init), before(ibefore) {}
T& operator*() { return current->value; }
const T& operator*() const { return current->value; }
fastListIterator<T>& operator++() { before = current; current = current->next; return *this;}
fastListIterator<T> operator++(int) {fastListIterator<T> bak=*this; before = current; current = current->next; return bak; }
bool operator ==(const fastListIterator<T>& that) const { return this->current == that.current; }
bool operator !=(const fastListIterator<T>& that) const { return this->current != that.current; }
fastListElement<T>* before;
fastListElement<T>* current;
protected:
};
template<class T> class fastList
{
public:
fastList() { cMemPool = cMemPoolBase = new char[1*1024*1024]; memset(cMemPool, 0, 1*1024*1024); head = tail = 0; }
~fastList() { delete cMemPoolBase; }
fastListIterator<T> begin() { return fastListIterator<T>(head, 0); }
fastListIterator<T> end() { return fastListIterator<T>(0, tail); }
fastListIterator<T> insert(const fastListIterator<T>& before, const T& value)
{
fastListElement<T>* elem=i_newElement();
elem->value = value;
if(before.before)
{
elem->next = before.current;
before.before->next = elem;
if(tail->next == elem)
tail = elem;
}
else
{
head = elem;
head->next = before.current;
if(tail == 0)
tail = elem;
}
return fastListIterator<T>(elem, before.before);
}
protected:
fastListElement<T>* i_newElement() { fastListElement<T>* ret = (fastListElement<T>*)cMemPool; cMemPool += sizeof(fastListElement<T>); return ret; }
fastListElement<T> *head, *tail;
char *cMemPool, *cMemPoolBase;
};
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 fastList<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://e...content-available-to-author-only...a.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://w...content-available-to-author-only...t.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, bool print=false)
{
// 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;
{ // force local scope - to clear up the containers at exit
NumbersInList list;
smarter_list_time = linearSmartInsertPerformance(values, list);
if(print)
std::for_each(list.begin(), list.end(), [&](Number& n) { std::cout << "lst: " << n << "\n"; });
}
{
NumbersInList list;
list_time = linearInsertPerformance(values, list);
if(print)
std::for_each(list.begin(), list.end(), [&](Number& n) { std::cout << "lst2: " << n << "\n"; });
}
{
NumbersInVector vector;
vector_time = linearInsertPerformance(values, vector);
if(print)
std::for_each(vector.begin(), vector.end(), [&](Number& n) { std::cout << "vec: " << n << "\n"; });
}
std::cout << nbr_of_randoms << ": " << std::flush;
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, true);
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;
std::cin.get();
return 0;
}