fork(1) download
copy 
  1. /** IMPORTANT UPDATE: 
  2.     This implementation contains two serious FLAWS. 
  3.     INSTEAD you should see how it is done correctly at: http://i...content-available-to-author-only...e.com/JOJ05
  4.     
  5.     1. Using indexes to iterate over a linked-list is BAD. The index value need to be calculated for each index update. 
  6.  
  7.     2. Using ArrayList but treating it as a List incurs sever overhead. 
  8.  
  9.     CORRECTING: Both fixes a lot of performance issues. There will still be a factor 2-3 times slower linked-list then ArrayList 
  10. */
  11.  
  12.  
  13. /**
  14.  * Java example of the original C++ std::vector vs std::list comparison. 
  15.  * Insertion of random elements, after linear traversal to get to the right position. 
  16.  * Insertion in sorted order. 
  17.  *
  18.  * Java version of C++ std::vector (dynamic array) is ArrayList
  19.  * Java version of C++ std::list (linked list) is LinkedList
  20.  *
  21.  * The original author was George Aristy. The code was hacked by KjellKod
  22.  * to use in codeproject article. This code was originally a java blog response from   
  23.  * http://l...content-available-to-author-only...t.com/2012/03/performance-comparison-linked-list-vs.html?m=1  */
  24.  
  25. import java.util.ArrayList;
  26. import java.util.Date;
  27. import java.util.LinkedList;
  28. import java.util.List;
  29. import java.util.Random;
  30. import java.util.Vector;
  31. /**
  32.  * Original author was George Aristy but hacked by KjellKod
  33.  * to use in codeproject article.
  34.  */
  35. public class Main {
  36.  
  37.   /**
  38.    * @param args the command line arguments
  39.    */
  40.   public static void main(String[] args) throws Exception {
  41.   try{
  42.       print("Compare silly-linear sorted insertion of random values: Times in microseconds (us)");
  43.       print("#Elements,  LinkedList,       ArrayList,      Vector");
  44.  
  45.    listVsVectorLinearPerformance(100);
  46.    listVsVectorLinearPerformance(200);
  47.    listVsVectorLinearPerformance(500);
  48.    listVsVectorLinearPerformance(1000);
  49.    listVsVectorLinearPerformance(2000);
  50.    listVsVectorLinearPerformance(3000);
  51.    listVsVectorLinearPerformance(4000);
  52.  
  53.    }
  54.    finally { /* */ }
  55. }
  56.  
  57.    private static void listVsVectorLinearPerformance(int size) {
  58.     // TODO code application logic here
  59.     int arraySize = size;
  60.     int maxArraySize = size;
  61.     Date now = new Date();
  62.     do {
  63. 	      Integer[] array = new Integer[arraySize];
  64. 	      Random random = new Random(123456789L);
  65. 	      LinkedList<Integer> linkedList = new LinkedList<Integer>();
  66.         linkedList.add(-1);
  67.         ArrayList<Integer> arrayList = new ArrayList<Integer>();
  68.         arrayList.add(-1);
  69. 	      Vector<Integer> vector = new Vector<Integer>();
  70.         vector.add(-1);
  71.  
  72. 	      for(int i = 0; i < array.length; i++){
  73. 	        array[i] = random.nextInt(Integer.MAX_VALUE);
  74. 	      }
  75.  
  76. 	      long before = System.nanoTime();
  77. 	      linearInsertion(array, linkedList);
  78. 	      long linkedListTime =  (System.nanoTime() - before)/1000;
  79.  
  80.         before = System.nanoTime();
  81.         linearInsertion(array, arrayList);
  82.         long arrayListTime = (System.nanoTime() - before)/1000;
  83.  
  84. 	      before = System.nanoTime();
  85. 	      linearInsertion(array, vector);
  86. 	      Long vectorTime = (System.nanoTime() - before)/1000;
  87.  
  88.         print(arraySize + ",\t\t" + linkedListTime + ",\t\t" + arrayListTime + "\t     " + vectorTime);
  89. 	      arraySize+=10000;
  90. 	    }while(arraySize <= maxArraySize);
  91.  
  92.       //print("Elapsed time (ms): " + (new Date().getTime() - now.getTime()));
  93.       //print("");
  94.  
  95.   }
  96.  
  97.  
  98.  
  99.   private static void linearInsertion(Integer[] intArray, List<Integer> list){
  100.     for(Integer integer : intArray){
  101. /*int list_size = list.size();*/
  102.       for(int i = 0; i < list.size(); i++){
  103.         if(integer.compareTo(list.get(i)) >= 0){
  104.           list.add(i, integer);
  105.           break;
  106.         }
  107.       }
  108.     }
  109.   }
  110.  
  111.   private static void print(String msg){
  112. 	  System.out.println(msg);
  113.   }
  114. }
  115.  
Success #stdin #stdout 10.35s 245952KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Compare silly-linear sorted insertion of random values: Times in microseconds (us)
#Elements,  LinkedList,       ArrayList,      Vector
100,		1759,		1536	     746
200,		1220,		510	     775
500,		13261,		2777	     4519
1000,		92707,		11218	     17445
2000,		689986,		39166	     63516
3000,		2370456,		89414	     143530
4000,		6352645,		158519	     255431
https://ideone.com/u5wbd
language:
Java (HotSpot 12)
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!