fork(1) 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://en.wikipedia.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://www2.research.att.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
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)