fork download
  1.  
Success #stdin #stdout 9.77s 3124KB
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,	 , 16, 15,		22, 9
200,	 , 33, 35,		33, 19
500,	 , 134, 153,		131, 66
1000,	 , 550, 513,		451, 185
4000,	 , 6809, 7318,		5900, 2081
10000,	 , 100421, 44943,		110069, 11790
20000,	 , 589209, 182490,		606982, 46515
40000,	 , 3430062, 797146,		3638707, 250067
Exiting test,. the whole measuring took 9837 milliseconds (9seconds or 0 minutes)