fork(3) download
  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
stdin
Standard input is empty
stdout
#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