fork(1) download
copy 
  1. import java.util.ArrayList;
  2. import java.util.Arrays;
  3. import java.util.LinkedList;
  4. import java.util.List;
  5. import java.util.ListIterator;
  6. import java.util.Random;
  7. import java.util.Vector;
  8.  
  9. public class Main {
  10.  
  11. 	static class Result {
  12. 		int size;
  13. 		long linkedListTime;
  14. 		long arrayListTime;
  15. 		long vectorTime;
  16.  
  17. 		public Result(int size) {
  18. 			this.size = size;
  19. 		}
  20. 	}
  21.  
  22. 	public static void main(String[] args) throws Exception {
  23.  
  24. 		// warm up code to make the benchmark more accurate
  25. 		for (int i = 0; i < 100; i++)
  26. 			listVsVectorLinearPerformance(1000);
  27.  
  28. 		// print the header
  29. 		System.out.printf("%-15s %-20s %-20s %-20s%n", 
  30. 						  "#Elements",  "LinkedList", "ArrayList", "Vector");
  31.  
  32. 		// perform the benchmarking
  33. 		printResult(listVsVectorLinearPerformance(100));
  34. 		printResult(listVsVectorLinearPerformance(200));
  35. 		printResult(listVsVectorLinearPerformance(500));
  36. 		printResult(listVsVectorLinearPerformance(1000));
  37. 		printResult(listVsVectorLinearPerformance(2000));
  38. 		printResult(listVsVectorLinearPerformance(3000));
  39. 		printResult(listVsVectorLinearPerformance(4000));
  40. 	}
  41.  
  42. 	private static void printResult(Result r) {
  43.  
  44. 		long min = Math.min(r.linkedListTime, Math.min(r.arrayListTime, r.vectorTime));
  45.  
  46. 		System.out.printf("%-15d %-10d (%-3.0f%%)    %-10d (%-3.0f%%)    %-10d (%-3.0f%%)%n", 
  47. 				r.size, 
  48. 				r.linkedListTime, (100 * (double) r.linkedListTime) / min,
  49. 				r.arrayListTime,  (100 * (double) r.arrayListTime) / min,
  50. 				r.vectorTime,     (100 * (double) r.vectorTime) / min);
  51. 	}
  52.  
  53. 	private static Result listVsVectorLinearPerformance(int size) {
  54.  
  55. 		Integer[] array = new Integer[size];
  56. 		Random random = new Random(123456789L);
  57.  
  58. 		LinkedList<Integer> linkedList = new LinkedList<Integer>(Arrays.asList(-1));
  59. 		ArrayList<Integer> arrayList = new ArrayList<Integer>(Arrays.asList(-1));
  60. 		Vector<Integer> vector = new Vector<Integer>(Arrays.asList(-1));
  61.  
  62. 		for (int i = 0; i < array.length; i++) 
  63. 			array[i] = random.nextInt(Integer.MAX_VALUE);
  64.  
  65. 		Result result = new Result(size);
  66.  
  67. 		long before = System.nanoTime();
  68. 		linearInsertion(array, linkedList);
  69. 		result.linkedListTime = (System.nanoTime() - before) / 1000;
  70.  
  71. 		before = System.nanoTime();
  72. 		linearInsertion(array, arrayList);
  73. 		result.arrayListTime = (System.nanoTime() - before) / 1000;
  74.  
  75. 		before = System.nanoTime();
  76. 		linearInsertion(array, vector);
  77. 		result.vectorTime = (System.nanoTime() - before) / 1000;
  78.  
  79. 		// check that they are equal
  80. 		if (!(linkedList.equals(arrayList) && arrayList.equals(vector)))
  81. 			throw new RuntimeException("Not equal...");
  82.  
  83. 		return result;
  84. 	}
  85.  
  86. 	private static void linearInsertion(Integer[] intArray, LinkedList<Integer> list) {
  87. 		for (Integer integer : intArray) {
  88. 			for (ListIterator<Integer> it = list.listIterator(); it.hasNext();) {
  89. 				if (integer.compareTo(it.next()) >= 0) {
  90. 					it.previous(); // should be added before element
  91. 					it.add(integer);
  92. 					break;
  93. 				}
  94. 			}
  95. 		}
  96. 	}
  97.  
  98. 	private static void linearInsertion(Integer[] intArray, List<Integer> list) {
  99. 		for (Integer integer : intArray) {
  100. 			for (int i = 0; i < list.size(); i++) {
  101. 				if (integer.compareTo(list.get(i)) >= 0) {
  102. 					list.add(i, integer);
  103. 					break;
  104. 				}
  105. 			}
  106. 		}
  107. 	}
  108. }
  109.  
Success #stdin #stdout 3.89s 245824KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
#Elements       LinkedList           ArrayList            Vector              
100             48         (100%)    106        (221%)    168        (350%)
200             170        (100%)    387        (228%)    634        (373%)
500             1074       (100%)    2396       (223%)    3813       (355%)
1000            4205       (100%)    9188       (219%)    15394      (366%)
2000            21644      (100%)    37752      (174%)    61065      (282%)
3000            50746      (100%)    88788      (175%)    140285     (276%)
4000            86339      (100%)    153911     (178%)    249794     (289%)
https://ideone.com/lmNDj
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!