fork download
copy 
  1. /* SMART Linked-list vs "normal" linked-list vs Vector. 15seconds maximum run-time 
  2. Linear search and sorted insertion. std::list remembers last position to 
  3. minimize overhead in traversing the list.*/
  4.  
  5. #include <list>
  6. #include <vector>
  7. #include <iostream>
  8. #include <iomanip>
  9. #include <random>
  10. #include <functional>
  11. #include <iostream>
  12. #include <chrono>
  13. #include <string>
  14. #include <numeric>
  15. #include <algorithm>
  16. #include <cassert>
  17. #include <string.h>
  18.  
  19. template < class T> struct fastListElement
  20. {
  21. public:
  22.     T value;
  23.     fastListElement<T>* next;
  24. };
  25.  
  26. template < class T> class fastListIterator
  27. {
  28. public:
  29.     fastListIterator(fastListElement<T>* init, fastListElement<T>* ibefore): current(init), before(ibefore) {}
  30.     T& operator*() { return current->value; }
  31.     const T& operator*() const { return current->value; }
  32.     fastListIterator<T>& operator++() { before = current; current = current->next; return *this;}
  33.     fastListIterator<T> operator++(int) {fastListIterator<T> bak=*this; before = current; current = current->next; return bak; }
  34.     bool operator ==(const fastListIterator<T>& that) const { return this->current == that.current; }
  35. 	bool operator !=(const fastListIterator<T>& that) const { return this->current != that.current; }
  36.  
  37. 	fastListElement<T>* before;
  38. 	fastListElement<T>* current;
  39. protected:
  40.  
  41. };
  42.  
  43. template<class T> class fastList
  44. {
  45. public:
  46.     fastList() { cMemPool = cMemPoolBase = new char[1*1024*1024]; memset(cMemPool, 0, 1*1024*1024); head = tail = 0; }
  47.     ~fastList() { delete cMemPoolBase; }
  48.     fastListIterator<T> begin() { return fastListIterator<T>(head, 0); }    
  49.     fastListIterator<T> end() { return fastListIterator<T>(0, tail); }    
  50. 	fastListIterator<T> insert(const fastListIterator<T>& before, const T& value) 
  51. 	{ 
  52. 		fastListElement<T>* elem=i_newElement(); 	
  53. 		elem->value = value; 
  54. 		if(before.before)
  55. 		{
  56. 			elem->next = before.current;
  57. 			before.before->next = elem;
  58. 			if(tail->next == elem)
  59. 				tail = elem;
  60. 		}
  61. 		else
  62. 		{
  63. 			head = elem;
  64. 			head->next = before.current;
  65. 			if(tail == 0)
  66. 				tail = elem;
  67. 		}
  68.  
  69. 		return fastListIterator<T>(elem, before.before);
  70. 	}
  71. protected:
  72.     fastListElement<T>* i_newElement() { fastListElement<T>* ret = (fastListElement<T>*)cMemPool; cMemPool += sizeof(fastListElement<T>); return ret; }
  73.     fastListElement<T> *head, *tail;
  74.     char *cMemPool, *cMemPoolBase;
  75. };
  76.  
  77.  
  78. namespace g2
  79. {       
  80.   typedef std::chrono::high_resolution_clock clock;
  81.   typedef std::chrono::microseconds microseconds;
  82.   typedef std::chrono::milliseconds milliseconds;
  83.  
  84.   clock::time_point now(){return clock::now();}
  85.  
  86.   microseconds intervalUs(const clock::time_point& t1, const clock::time_point& t0)
  87.   {return std::chrono::duration_cast<microseconds>(t1 - t0);}
  88.  
  89.   milliseconds intervalMs(const clock::time_point& t1,const clock::time_point& t0)
  90.   {return std::chrono::duration_cast<milliseconds>(t1 - t0);}
  91.  
  92.  
  93.   class StopWatch
  94.   {
  95.     clock::time_point start_;
  96.   public:
  97.     StopWatch() : start_(clock::now()){}
  98.     clock::time_point restart()         { start_ = clock::now(); return start_;}
  99.     microseconds elapsedUs()            { return intervalUs(now(), start_);}
  100.     milliseconds elapsedMs()            {return intervalMs(now(), start_);}
  101.   };
  102. } // g2
  103.  
  104.  
  105.  
  106.  
  107.  
  108. typedef unsigned int  Number;
  109. typedef fastList<Number>           NumbersInList;
  110. typedef std::vector<Number>         NumbersInVector;
  111. typedef long long int               TimeValue;
  112.  
  113.  
  114. /*   // Lambda expression for generating a random number using the 'mersenne twister distribution'
  115.      // http://e...content-available-to-author-only...a.org/wiki/Mersenne_twister
  116. auto random_int = [&](const Number& low, const Number& high) -> Number {
  117.     std::uniform_int_distribution<int> distribution(low, high);
  118.     std::mt19937 engine((unsigned int)time(0)); // Mersenne twister MT19937
  119.     auto generator = std::bind(distribution, engine);
  120.     return generator();
  121. };   */
  122.  
  123. // Random integer function from http://w...content-available-to-author-only...t.com/~bs/C++0xFAQ.html#std-random
  124. int random_int(int low, int high)
  125. {
  126.   using namespace std;
  127.  
  128.   static default_random_engine engine {};
  129.   typedef uniform_int_distribution<int> Distribution;
  130.   static Distribution distribution {};
  131.  
  132.   return distribution(engine, Distribution::param_type{low, high});
  133. }
  134.  
  135.  
  136.  
  137.  
  138.  
  139.  
  140. // Use a template approach to use functor, function pointer or lambda to insert an
  141. // element in the input container and return the "time result".
  142. // Search is LINEAR. Elements are insert in SORTED order
  143. template<typename Container>
  144. void linearInsertion(const NumbersInVector& numbers, Container& container)
  145. {
  146.     std::for_each(numbers.begin(), numbers.end(),
  147.                   [&](const Number& n)
  148.     {
  149.         auto itr = container.begin();
  150.         for (; itr!= container.end(); ++itr)
  151.         {
  152.             if ((*itr) >= n) {
  153.                 break;
  154.             }
  155.         }
  156.         container.insert(itr, n);
  157.     });
  158. }
  159.  
  160. namespace{
  161. // A little bit smarter --- remembers the last insertion point's position and can 
  162. // start from that if wanted-position is >= last-position: this is calculated from the values
  163. // and not from the absolute positions
  164. TimeValue linearSmartInsertPerformance(const NumbersInVector& numbers, NumbersInList& container)
  165. {
  166.     g2::StopWatch watch; 
  167.     auto last_inserted_value = 0;
  168.     auto last_iter_position = container.begin();
  169.  
  170.     std::for_each(numbers.begin(), numbers.end(),
  171.                   [&](const Number& n)
  172.     {
  173.         auto itr = container.begin();
  174.         if(n >= last_inserted_value)
  175.         {
  176.            itr = last_iter_position;
  177.         }
  178.  
  179.         for (; itr!= container.end(); ++itr)
  180.         {
  181.             if ((*itr) >= n) {
  182.                 break;
  183.             }
  184.         }
  185.         last_iter_position = container.insert(itr, n);
  186.         last_inserted_value = n;
  187.     });
  188.     auto time = watch.elapsedUs().count();
  189.     return time;
  190. }
  191. } // anonymous namespace
  192.  
  193. // Measure time in milliseconds for linear insert in a std container
  194. template<typename Container>
  195. TimeValue linearInsertPerformance(const NumbersInVector& randoms, Container& container)
  196. {
  197.     g2::StopWatch watch;
  198.     linearInsertion(std::cref(randoms), container);
  199.     auto time = watch.elapsedUs().count();
  200.     return time;
  201. }
  202.  
  203.  
  204. void listVsVectorLinearPerformance(size_t nbr_of_randoms, bool print=false)
  205. {
  206.   // Generate n random values and push to storage
  207.   NumbersInVector     values(nbr_of_randoms);
  208.   std::for_each(values.begin(), values.end(), [&](Number& n) { n = random_int(0, nbr_of_randoms -1);}); 
  209.   //print_distribution(values); 
  210.  
  211.   TimeValue smarter_list_time;
  212.   TimeValue list_time;
  213.   TimeValue vector_time;    
  214.  
  215.  
  216.  
  217.   { // force local scope - to clear up the containers at exit	
  218.     NumbersInList      list;
  219.     smarter_list_time = linearSmartInsertPerformance(values, list);
  220. 	if(print)
  221. 		std::for_each(list.begin(), list.end(), [&](Number& n) { std::cout << "lst: " << n << "\n"; });
  222.   }
  223.   {
  224.     NumbersInList      list;
  225.     list_time = linearInsertPerformance(values, list);
  226. 	if(print)
  227. 		std::for_each(list.begin(), list.end(), [&](Number& n) { std::cout << "lst2: " << n << "\n"; });
  228.   }
  229.   {
  230.     NumbersInVector    vector;
  231.     vector_time = linearInsertPerformance(values, vector);
  232. 	if(print)
  233. 		std::for_each(vector.begin(), vector.end(), [&](Number& n) { std::cout << "vec: " << n << "\n"; });
  234.   }
  235.  
  236.   std::cout << nbr_of_randoms << ": " << std::flush;
  237.   std::cout <<  smarter_list_time << ", " << list_time << ", " << vector_time << std::endl << std::flush;
  238. }
  239.  
  240.  
  241. int main(int argc, char** argv)
  242. {
  243. std::cout << "\n\n********** Times in microseconds**********" << std::endl;
  244. std::cout << "Elements ADD (Smarter-List,   List,    Vector)" << std::endl;
  245.  
  246.  
  247.  
  248.   g2::StopWatch watch; // only 15seconds available, therefore the short ranges
  249.   listVsVectorLinearPerformance(10, true);
  250.   listVsVectorLinearPerformance(100);
  251.   listVsVectorLinearPerformance(500);
  252.   listVsVectorLinearPerformance(1000);
  253.   listVsVectorLinearPerformance(2000);
  254.   listVsVectorLinearPerformance(3000);
  255.   listVsVectorLinearPerformance(4000);
  256.   listVsVectorLinearPerformance(6000);
  257.   listVsVectorLinearPerformance(8000);
  258.   listVsVectorLinearPerformance(16000);
  259.   listVsVectorLinearPerformance(32000);
  260.   auto total_time_ms = watch.elapsedMs().count();
  261.  
  262.  
  263.  
  264.   std::cout << "Exiting test,. the whole measuring took " << total_time_ms << " milliseconds";
  265.   std::cout << " (" << total_time_ms/1000 << "seconds or " << total_time_ms/(1000*60) << " minutes)" << std::endl; 
  266.   std::cin.get();
  267.    return 0;
  268. }
Success #stdin #stdout 3.62s 3120KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 

********** Times in microseconds**********
Elements ADD (Smarter-List,   List,    Vector)
lst: 0
lst: 0
lst: 1
lst: 2
lst: 4
lst: 5
lst: 6
lst: 6
lst: 7
lst: 9
lst2: 0
lst2: 0
lst2: 1
lst2: 2
lst2: 4
lst2: 5
lst2: 6
lst2: 6
lst2: 7
lst2: 9
vec: 0
vec: 0
vec: 1
vec: 2
vec: 4
vec: 5
vec: 6
vec: 6
vec: 7
vec: 9
10: 0, 1, 7
100: 6, 7, 13
500: 86, 115, 170
1000: 323, 468, 621
2000: 1254, 1842, 2365
3000: 2831, 4163, 5275
4000: 4810, 7280, 9208
6000: 10978, 16571, 20790
8000: 19729, 29487, 36823
16000: 142842, 213366, 146772
32000: 913375, 1364017, 629861
Exiting test,. the whole measuring took 3627 milliseconds (3seconds or 0 minutes)
https://ideone.com/dYe4f7
language:
C++14 (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!