fork(4) download
copy 
  1. /*
  2. Code example for the blog entry  "Java Battle Royal: LinkedList vs ArrayList vs DynamicIntArray"
  3. This code example is a "silly" linear search then insertion to prove a point. 
  4.  
  5. This code shows Davids java example (corrected), which shows that LinkedList is 
  6. comparible to ArrayList. Even though this is a NAIVE use of ArrayList
  7.  
  8. The ArrayList used here is still SUBOPTIMAL 
  9.     1) random_access is not used 
  10.     2) It is called through its parent API List<integer> instead of ArrayList<integer> (HUGE difference)
  11.  
  12. For a corrected version that actually USES the cache friendliness of ArrayList
  13.   please see : http://i...content-available-to-author-only...e.com/JOJ05
  14.   which COMPLETELY blow away LinkedList performance wise
  15.  
  16.  
  17. i.e. http://k...content-available-to-author-only...s.com/2012/08/08/java-galore-linkedlist-vs-arraylist-vs-dynamicintarray/
  18. */
  19.  
  20. import java.util.ArrayList;
  21. import java.util.Arrays;
  22. import java.util.LinkedList;
  23. import java.util.List;
  24. import java.util.ListIterator;
  25. import java.util.Random;
  26. import java.util.Vector;
  27.  
  28. public class Main {
  29.  
  30. 	static class Result {
  31. 		int size;
  32. 		long linkedListTime;
  33. 		long arrayListTime;
  34. 		long vectorTime;
  35.  
  36. 		public Result(int size) {
  37. 			this.size = size;
  38. 		}
  39. 	}
  40.  
  41. 	public static void main(String[] args) throws Exception {
  42.  
  43. 		// warm up code to make the benchmark more accurate
  44. 		for (int i = 0; i < 100; i++)
  45. 			listVsVectorLinearPerformance(1000);
  46.  
  47. 		// print the header
  48. 		System.out.printf("%-15s %-20s %-20s %-20s%n", 
  49. 						  "#Elements",  "LinkedList", "ArrayList", "Vector");
  50.  
  51. 		// perform the benchmarking
  52. 		printResult(listVsVectorLinearPerformance(100));
  53. 		printResult(listVsVectorLinearPerformance(200));
  54. 		printResult(listVsVectorLinearPerformance(500));
  55. 		printResult(listVsVectorLinearPerformance(1000));
  56. 		printResult(listVsVectorLinearPerformance(2000));
  57. 		printResult(listVsVectorLinearPerformance(3000));
  58. 		printResult(listVsVectorLinearPerformance(4000));
  59. 		printResult(listVsVectorLinearPerformance(5000));
  60. 		printResult(listVsVectorLinearPerformance(10000));
  61.                 printResult(listVsVectorLinearPerformance(20000));
  62.  
  63.                 System.out.println("\n\nDavids java example (corrected), which shows that LinkedList is ");
  64.                 System.out.println("comparible to ArrayList. Even though this is a NAIVE use of ArrayList"); 
  65.                 System.out.println("\nThe ArrayList used here is still SUBOPTIMAL ");
  66.                 System.out.println("    1) random_access is not used ");
  67.                 System.out.println("    2) It is called through its parent API List<integer> instead of ArrayList<integer> (HUGE difference)");
  68.                 System.out.println("\nFor a corrected version that actually USES the cache friendliness of ArrayList");
  69.                 System.out.println("  please see : http://i...content-available-to-author-only...e.com/JOJ05"); 
  70.                 System.out.println("  which COMPLETELY blow away LinkedList performance wise");
  71.  
  72.  
  73. 	}
  74.  
  75. 	private static void printResult(Result r) {
  76.  
  77. 		long min = Math.min(r.linkedListTime, Math.min(r.arrayListTime, r.vectorTime));
  78.  
  79. 		System.out.printf("%-15d %-10d (%-3.0f%%)    %-10d (%-3.0f%%)    %-10d (%-3.0f%%)%n", 
  80. 				r.size, 
  81. 				r.linkedListTime, (100 * (double) r.linkedListTime) / min,
  82. 				r.arrayListTime,  (100 * (double) r.arrayListTime) / min,
  83. 				r.vectorTime,     (100 * (double) r.vectorTime) / min);
  84. 	}
  85.  
  86. 	private static Result listVsVectorLinearPerformance(int size) {
  87.  
  88. 		Integer[] array = new Integer[size];
  89. 		Random random = new Random(123456789L);
  90.  
  91. 		LinkedList<Integer> linkedList = new LinkedList<Integer>(Arrays.asList(-1));
  92. 		ArrayList<Integer> arrayList = new ArrayList<Integer>(Arrays.asList(-1));
  93. 		Vector<Integer> vector = new Vector<Integer>(Arrays.asList(-1));
  94.  
  95. 		for (int i = 0; i < array.length; i++) 
  96. 			array[i] = random.nextInt(Integer.MAX_VALUE);
  97.  
  98. 		Result result = new Result(size);
  99.  
  100. 		long before = System.nanoTime();
  101. 		linearInsertion(array, linkedList);
  102. 		result.linkedListTime = (System.nanoTime() - before) / 1000;
  103.  
  104. 		before = System.nanoTime();
  105. 		linearInsertion(array, arrayList);
  106. 		result.arrayListTime = (System.nanoTime() - before) / 1000;
  107.  
  108. 		before = System.nanoTime();
  109. 		linearInsertion(array, vector);
  110. 		result.vectorTime = (System.nanoTime() - before) / 1000;
  111.  
  112. 		// check that they are equal
  113. 		if (!(linkedList.equals(arrayList) && arrayList.equals(vector)))
  114. 			throw new RuntimeException("Not equal...");
  115.  
  116. 		return result;
  117. 	}
  118.  
  119. 	private static void linearInsertion(Integer[] intArray, LinkedList<Integer> list) {
  120. 		for (Integer integer : intArray) {
  121. 			for (ListIterator<Integer> it = list.listIterator(); it.hasNext();) {
  122. 				if (integer.compareTo(it.next()) >= 0) {
  123. 					it.previous(); // should be added before element
  124. 					it.add(integer);
  125. 					break;
  126. 				}
  127. 			}
  128. 		}
  129. 	}
  130.  
  131. 	private static void linearInsertion(Integer[] intArray, List<Integer> list) {
  132.  		for (Integer integer : intArray) {
  133.                         int list_size = list.size(); // avoid calculating the size every time
  134. 			for (int i = 0; i < list_size; i++) {
  135. 				if (integer.compareTo(list.get(i)) >= 0) {
  136. 					list.add(i, integer);
  137. 					break;
  138. 				}
  139. 			}
  140. 		}
  141. 	}
  142. }
Success #stdin #stdout 14.04s 245888KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
#Elements       LinkedList           ArrayList            Vector              
100             50         (100%)    95         (190%)    112        (224%)
200             178        (100%)    258        (145%)    384        (216%)
500             1096       (100%)    1474       (134%)    2234       (204%)
1000            4269       (100%)    5631       (132%)    8725       (204%)
2000            20064      (100%)    22117      (110%)    33973      (169%)
3000            49056      (100%)    50446      (103%)    76825      (157%)
4000            88585      (100%)    90387      (102%)    143283     (162%)
5000            143501     (100%)    143434     (100%)    220160     (153%)
10000           669422     (115%)    582517     (100%)    937818     (161%)
20000           3992467    (175%)    2466246    (108%)    2283358    (100%)


Davids java example (corrected), which shows that LinkedList is 
comparible to ArrayList. Even though this is a NAIVE use of ArrayList

The ArrayList used here is still SUBOPTIMAL 
    1) random_access is not used 
    2) It is called through its parent API List<integer> instead of ArrayList<integer> (HUGE difference)

For a corrected version that actually USES the cache friendliness of ArrayList
  please see : http://i...content-available-to-author-only...e.com/JOJ05
  which COMPLETELY blow away LinkedList performance wise
https://ideone.com/1wnF1
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!