fork(7) download 
  1. // Vector vs LinkedList. Random element and linear traversal to 
  2. // get to the right position. Insertion gives sorted order.
  3.  
  4. #include <list>
  5. #include <vector>
  6. #include <iostream>
  7. #include <iomanip>
  8. #include <functional>
  9. #include <random>
  10. #include <iostream>
  11. #include <chrono>
  12. #include <string>
  13. #include <numeric>
  14. #include <algorithm>
  15. #include <cassert>
  16.  
  17. namespace g2
  18. {       
  19.   typedef std::chrono::high_resolution_clock clock;
  20.   typedef std::chrono::microseconds microseconds;
  21.   typedef std::chrono::milliseconds milliseconds;
  22.  
  23.   clock::time_point now(){return clock::now();}
  24.  
  25.   microseconds intervalUs(const clock::time_point& t1, const clock::time_point& t0)
  26.   {return std::chrono::duration_cast<microseconds>(t1 - t0);}
  27.  
  28.   milliseconds intervalMs(const clock::time_point& t1,const clock::time_point& t0)
  29.   {return std::chrono::duration_cast<milliseconds>(t1 - t0);}
  30.  
  31.  
  32.   class StopWatch
  33.   {
  34.     clock::time_point start_;
  35.   public:
  36.     StopWatch() : start_(clock::now()){}
  37.     clock::time_point restart()         { start_ = clock::now(); return start_;}
  38.     microseconds elapsedUs()            { return intervalUs(now(), start_);}
  39.     milliseconds elapsedMs()            {return intervalMs(now(), start_);}
  40.   };
  41. } // g2
  42.  
  43.  
  44.  
  45.  
  46.  
  47. typedef unsigned int  Number;
  48. typedef std::list<Number>           NumbersInList;
  49. typedef std::vector<Number>         NumbersInVector;
  50. typedef long long int               TimeValue;
  51.  
  52.  
  53. /*   // Lambda expression for generating a random number using the 'mersenne twister distribution'
  54.      // http://e...content-available-to-author-only...a.org/wiki/Mersenne_twister
  55. auto random_int = [&](const Number& low, const Number& high) -> Number {
  56.     std::uniform_int_distribution<int> distribution(low, high);
  57.     std::mt19937 engine((unsigned int)time(0)); // Mersenne twister MT19937
  58.     auto generator = std::bind(distribution, engine);
  59.     return generator();
  60. };   */
  61.  
  62. // Random integer function from http://w...content-available-to-author-only...t.com/~bs/C++0xFAQ.html#std-random
  63. int random_int(int low, int high)
  64. {
  65.   using namespace std;
  66.  
  67.   static default_random_engine engine {};
  68.   typedef uniform_int_distribution<int> Distribution;
  69.   static Distribution distribution {};
  70.  
  71.   return distribution(engine, Distribution::param_type{low, high});
  72. }
  73.  
  74.  
  75. // test printout just to see the distribution
  76. void print_distribution(std::vector<Number>& values)
  77. {  
  78.   for (int i = 0; i<values.size(); ++i) 
  79.   {
  80.     std::cout << i << '\t';
  81.     for (int j=0; j<values[i]; ++j) std::cout << '*';
  82.     std::cout << '\n';
  83.   }
  84. }
  85.  
  86.  
  87.  
  88.  
  89. // Use a template approach to use functor, function pointer or lambda to insert an
  90. // element in the input container and return the "time result".
  91. // Search is LINEAR. Elements are insert in SORTED order
  92. template<typename Container>
  93. void linearInsertion(const NumbersInVector& numbers, Container& container)
  94. {
  95.     std::for_each(numbers.begin(), numbers.end(),
  96.                   [&](const Number& n)
  97.     {
  98.         auto itr = container.begin();
  99.         for (; itr!= container.end(); ++itr)
  100.         {
  101.             if ((*itr) >= n) {
  102.                 break;
  103.             }
  104.         }
  105.         container.insert(itr, n);
  106.     });
  107. }
  108.  
  109. // Measure time in milliseconds for linear insert in a std container
  110. template<typename Container>
  111. TimeValue linearInsertPerformance(const NumbersInVector& randoms, Container& container)
  112. {
  113.     g2::StopWatch watch;
  114.     linearInsertion(std::cref(randoms), container);
  115.     auto time = watch.elapsedUs().count();
  116.     return time;
  117. }
  118.  
  119.  
  120.  
  121. // Delete of an element from a std container. The Delete of an item is from a random position.
  122. template<typename Container>
  123. void linearErase(Container& container)
  124. {
  125.     // Possibly O(n) to get initially but we use it for the random number generation
  126.     //    and it is only done ONCE
  127.     auto size = container.size();
  128.     while (false == container.empty())
  129.     {
  130.         // force silly linear search to the right position to do a delete
  131.         Number random_position = random_int(0, size -1);
  132.         auto itr = container.begin();
  133.  
  134.         // using hand-wrought 'find' to force linear search to the position
  135.         for (unsigned int idx = 0; idx != random_position; ++idx)
  136.         {
  137.             ++itr; // silly linear
  138.         }
  139.         container.erase(itr);
  140.         --size;
  141.     }
  142. }
  143.  
  144. // Measure time in milliseconds for linear remove (i.e. "erase") in a std container
  145. template<typename Container>
  146. TimeValue linearRemovePerformance(Container& container)
  147. {
  148.     g2::StopWatch watch;
  149.     linearErase(container);
  150.     auto time = watch.elapsedUs().count();
  151.     return time;
  152. }
  153.  
  154.  
  155. void listVsVectorLinearPerformance(size_t nbr_of_randoms)
  156. {
  157.   // Generate n random values and push to storage
  158.   NumbersInVector     values(nbr_of_randoms);
  159.   std::for_each(values.begin(), values.end(), [&](Number& n) { n = random_int(0, nbr_of_randoms -1);}); 
  160.   //print_distribution(values); 
  161.  
  162.   TimeValue list_time;
  163.   TimeValue list_delete_time;
  164.   TimeValue vector_time;    
  165.   TimeValue vector_delete_time;
  166.   std::cout << nbr_of_randoms << ",\t" << std::flush;
  167.  
  168.  
  169.   { // force local scope - to clear up the containers at exit	
  170.     NumbersInList      list;
  171.     list_time = linearInsertPerformance(values, list);
  172.     list_delete_time = linearRemovePerformance(list);
  173.   }
  174.   {
  175.     NumbersInVector    vector;
  176.     vector_time = linearInsertPerformance(values, vector);
  177.     std::cout << " "  << ", ";
  178.     vector_delete_time = linearRemovePerformance(vector);
  179.   }
  180.   std::cout <<  list_time << ", " << vector_time << ",";
  181.   std::cout << "\t\t" << list_delete_time << ", " << vector_delete_time << std::endl << std::flush;
  182. }
  183.  
  184.  
  185.  
  186.  
  187. // Used for debugging and verification, 
  188. // normally disabled
  189. template<typename Container>
  190. void printValues(const std::string& msg, const Container& values)
  191. {
  192.   std::cout << msg << std::endl;
  193.   std::for_each(values.begin(), values.end(),
  194.     [&](const Number& n) { std::cout << " " << n << " "; }); 
  195.  
  196.   std::cout << "\n" << std::endl;
  197. }
  198.  
  199.  
  200.  
  201. // disabled normally,. only used to verify during dev,time not test,time
  202. template<typename ProspectLinear>
  203. void verifyLinearSort(const NumbersInVector& valid_container, const ProspectLinear& container)
  204. {
  205.   auto toCheckItr = container.begin();
  206.   std::for_each(valid_container.begin(), valid_container.end(),
  207.     [&](const Number& n)
  208.   {
  209.     assert(toCheckItr != container.end());
  210.     Number n2 = (*toCheckItr);
  211.     if(n != n2)
  212.     {
  213.       printValues("\nTrue Linear should be: ", valid_container);
  214.       printValues("\nError in comparison printing numbers: ", container);
  215.       std::cout << "check error: " << n << "vs value: " << n2 << std::endl;
  216.       assert(n == n2 && "not matching numbers");
  217.     }
  218.     ++toCheckItr;
  219.   });
  220. }
  221.  
  222.  
  223.  
  224. int main(int argc, char** argv)
  225. { 
  226.  
  227.   // Generate N random integers and insert them in its proper position in the numerical order using
  228.   // LINEAR search
  229.   std::cout << "Comparison of insert and erase (delete) of item from a linked list and vector (array)" << std::endl;
  230.   std::cout << "Insert is done on random item, with linear search to get to the insert position" << std::endl;
  231.   std::cout << "Erase is done on a random position within the available elements. Linear search to get to the position" << std::endl;
  232.   std::cout << "\n\n Linked-list shows close to exponential time usage in contrast to the vectors almost linear time usage"<< std::endl;
  233.   std::cout << "The HUGE difference is due to that a vector is sequential in memory and thereby is maximazing cache-line usage" << std::endl;
  234.  std::cout << "The linked-list uses RAM much more and cache-line misses are maximized. " << std::endl;
  235.  std::cout << "\n\n CONCLUSION: When comparing linked list and vector/array then the linear search COMPLETELY" << std::endl; 
  236.  std::cout << "DOMINATES the time consumption. Cache-line friendly data structures show much promise in speed" << std::endl;
  237.  std::cout << "The fact that a vector uses many memory shuffling when increasing, inserting deleting elements is of " << std::endl; 
  238. std::cout << "LIMITED importance compared to the RAM access slow-down for a linked-list" << std::endl;
  239.  
  240. std::cout << "\nFor test results on Windows and Linux please go to: " << std::endl;
  241. std::cout << "https://docs.google.com/spreadsheet/pub?key=0AkliMT3ZybjAdGJMU1g5Q0QxWEluWGRzRnZKZjNMMGc&output=html" << std::endl;
  242.  
  243. std::cout << "\n\n********** Times in microseconds**********" << std::endl;
  244. std::cout << "Elements ADD (List, Vector)\tERASE(List, Vector)" << std::endl;
  245. //[elements, linear add time [ms] [list, vector],    linear erase time[ms] [list, vector]" << std::endl;
  246.  
  247.   g2::StopWatch watch;
  248.   listVsVectorLinearPerformance(100);
  249.   listVsVectorLinearPerformance(200);
  250.   listVsVectorLinearPerformance(500);
  251.   listVsVectorLinearPerformance(1000);
  252.   listVsVectorLinearPerformance(4000);
  253.   listVsVectorLinearPerformance(10000);
  254.   listVsVectorLinearPerformance(20000);
  255.   listVsVectorLinearPerformance(40000);
  256.   auto total_time_ms = watch.elapsedMs().count();
  257.  
  258.   std::cout << "Exiting test,. the whole measuring took " << total_time_ms << " milliseconds";
  259.   std::cout << " (" << total_time_ms/1000 << "seconds or " << total_time_ms/(1000*60) << " minutes)" << std::endl; 
  260.    return 0;
  261. }
Success #stdin #stdout 11.26s 3592KB
comments (?)
stdin 
Standard input is empty
stdout 
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,	 , 15, 15,		16, 11
200,	 , 34, 36,		33, 20
500,	 , 155, 186,		134, 69
1000,	 , 548, 634,		460, 205
4000,	 , 7917, 9358,		5991, 2165
10000,	 , 105478, 58031,		114206, 12266
20000,	 , 617771, 234355,		628720, 48308
40000,	 , 3846772, 1008628,		4300509, 257546
Exiting test,. the whole measuring took 11265 milliseconds (11seconds or 0 minutes)
https://ideone.com/62Emz
language:
C++14 (gcc 8.3)
created:
10 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!