fork(2) download
  1. /*
  2. Code example for the blog entry
  3. "Java Battle Royal: LinkedList vs ArrayList vs DynamicIntArray"
  4.  
  5. "silly" linear search then insertion to prove a point.
  6. Java: Linked-list vs ArrayList vs DynamicIntArray. This code was an improved of David's (faulty) example (http://ideone.com/lmNDj)
  7.  
  8. i.e. http://kjellkod.wordpress.com/2012/08/08/java-galore-linkedlist-vs-arraylist-vs-dynamicintarray/
  9. */
  10.  
  11.  
  12. import java.util.ArrayList;
  13. import java.util.Arrays;
  14. import java.util.LinkedList;
  15. import java.util.List;
  16. import java.util.ListIterator;
  17. import java.util.Random;
  18. import java.util.Vector;
  19. import java.io.IOException;
  20.  
  21. public class Main {
  22.  
  23.  
  24.  
  25. class DynamicIntArray {
  26.  
  27. private int[] storage;
  28. private int size;
  29. private final int INITIAL_CAPACITY = 8;
  30. private final int GROW_FACTOR = 2;
  31.  
  32. private void rangeCheck(int index){
  33. if(index < 0 || index >= size)
  34. throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
  35. }
  36.  
  37. // ref: http://www.algolist.net/Data_structures/Dynamic_array/Capacity_management
  38. private void ensureCapacity(int size_wanted) {
  39. int max_capacity = storage.length;
  40. if (size_wanted > max_capacity) {
  41. max_capacity = max_capacity * GROW_FACTOR +1;
  42. // http://docs.oracle.com/javase/6/docs/api/java/util/Arrays.html#copyOf%28int[],%20int%29
  43. storage = Arrays.copyOf(storage, max_capacity); // increases array size + copy contents
  44. }
  45. }
  46.  
  47.  
  48. public DynamicIntArray() {
  49. storage = new int[INITIAL_CAPACITY];
  50. size = 0;
  51. }
  52. public int size() {return size;}
  53.  
  54. public boolean equals(List<Integer> list)
  55. {
  56. boolean success = (list.size() == size());
  57. if(success) {
  58. for(int idx = 0; success && (idx < size()); ++idx) {
  59. success = success && (get(idx) == list.get(idx).intValue());
  60. }
  61. }
  62. return success;
  63. }
  64.  
  65.  
  66. public int get(int position){
  67. rangeCheck(position);
  68. return storage[position];
  69. }
  70.  
  71. public void set(int index, int value){
  72. rangeCheck(index);
  73. storage[index] = value;
  74. }
  75.  
  76. public void add(int value) {
  77. insertAt(size, value); // same as c++ std::vector push_back
  78. }
  79.  
  80.  
  81. // Insert the value at the given index and shift 'tail' to give space.
  82. // The value can either be last position (size) or within the range 0 -> size.
  83. public void insertAt(int index, int value) {
  84. if(index < 0 || index > size) // allows for push_back to last index also
  85. throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
  86.  
  87. ensureCapacity(size+1);
  88. int move_count = size - index; // number of elements to shift
  89. if( move_count > 0)
  90. System.arraycopy(storage, index, storage, index+1, move_count);
  91.  
  92. storage[index] = value;
  93. size++;
  94. }
  95.  
  96. public void removeAt(int index) {
  97. rangeCheck(index);
  98. int move_count = size - index - 1;
  99. if (move_count > 0)
  100. System.arraycopy(storage, index + 1, storage, index, move_count);
  101.  
  102. size--;
  103. }
  104.  
  105.  
  106. public void printAll() {
  107. for (int idx = 0; idx < size; idx++)
  108. System.out.printf(" [%d]=%d", idx, get(idx));
  109.  
  110. System.out.println();
  111. }
  112. } // DynamicIntArray
  113.  
  114.  
  115.  
  116.  
  117. static class Result {
  118. int size;
  119. long linkedListTime;
  120. long arrayListTime;
  121. long dynamicArrayTime;
  122.  
  123. public Result(int size) {
  124. this.size = size;
  125. }
  126. }
  127.  
  128. public static void main(String[] args) throws Exception {
  129. Main obj = new Main();
  130.  
  131. // warm up code to make the benchmark more accurate
  132. for (int i = 0; i < 100; i++)
  133. obj.listVsVectorLinearPerformance(1000);
  134.  
  135. // print the header
  136. System.out.printf("%-15s %-20s %-20s %-20s%n",
  137. "#Elements", "LinkedList", "ArrayList", "DynamicArray");
  138.  
  139. // perform the benchmarking
  140. printResult(obj.listVsVectorLinearPerformance(100));
  141. printResult(obj.listVsVectorLinearPerformance(200));
  142. printResult(obj.listVsVectorLinearPerformance(500));
  143. printResult(obj.listVsVectorLinearPerformance(1000));
  144. printResult(obj.listVsVectorLinearPerformance(2000));
  145. printResult(obj.listVsVectorLinearPerformance(3000));
  146. printResult(obj.listVsVectorLinearPerformance(4000));
  147. printResult(obj.listVsVectorLinearPerformance(5000));
  148. printResult(obj.listVsVectorLinearPerformance(10000));
  149. // printResult(obj.listVsVectorLinearPerformance(20000)); // CPU time exceeded
  150.  
  151.  
  152. }
  153.  
  154. private static void printResult(Result r) {
  155.  
  156. long min = Math.min(r.linkedListTime, Math.min(r.arrayListTime, r.dynamicArrayTime));
  157.  
  158. System.out.printf("%-15d %-10d (%-3.0f%%) %-10d (%-3.0f%%) %-10d (%-3.0f%%)%n",
  159. r.size,
  160. r.linkedListTime, (100 * (double) r.linkedListTime) / min,
  161. r.arrayListTime, (100 * (double) r.arrayListTime) / min,
  162. r.dynamicArrayTime, (100 * (double) r.dynamicArrayTime) / min);
  163. }
  164.  
  165. private Result listVsVectorLinearPerformance(int size) {
  166.  
  167. Integer[] array = new Integer[size];
  168. Random random = new Random(123456789L);
  169.  
  170. LinkedList<Integer> linkedList = new LinkedList<Integer>(Arrays.asList(-1));
  171. ArrayList<Integer> arrayList = new ArrayList<Integer>(Arrays.asList(-1));
  172. DynamicIntArray dynamicArray = new DynamicIntArray();
  173. dynamicArray.add(-1);
  174.  
  175. for (int i = 0; i < array.length; i++)
  176. array[i] = random.nextInt(Integer.MAX_VALUE);
  177.  
  178. Result result = new Result(size);
  179.  
  180. long before = System.nanoTime();
  181. linearInsertion(array, linkedList);
  182. result.linkedListTime = (System.nanoTime() - before) / 1000;
  183.  
  184. before = System.nanoTime();
  185. linearInsertion(array, arrayList);
  186. result.arrayListTime = (System.nanoTime() - before) / 1000;
  187.  
  188. before = System.nanoTime();
  189. linearInsertionToDynamicArray(array, dynamicArray);
  190. result.dynamicArrayTime = (System.nanoTime() - before) / 1000;
  191.  
  192.  
  193. // check that they are equal
  194. if (!(linkedList.equals(arrayList) && dynamicArray.equals(arrayList)))
  195. throw new RuntimeException("Not equal...");
  196.  
  197. return result;
  198. }
  199.  
  200. private static void linearInsertion(Integer[] intArray, LinkedList<Integer> list) {
  201. for (Integer integer : intArray) {
  202. for (ListIterator<Integer> it = list.listIterator(); it.hasNext();) {
  203. if (integer.compareTo(it.next()) >= 0) {
  204. it.previous(); // should be added before element
  205. it.add(integer);
  206. break;
  207. }
  208. }
  209. }
  210. }
  211.  
  212. // 1. Avoid calling size() a lot makes actually a big difference
  213. // 2. NEVER use iterators to loop through and ArrayList. Random access is so much faster
  214. // ref: http://docs.oracle.com/javase/1.4.2/docs/api/java/util/RandomAccess.html
  215. private static void linearInsertion(Integer[] intArray, ArrayList<Integer> list) {
  216. for (Integer integer : intArray) {
  217. int list_size = list.size(); // on purpose: it is smarter to avoid calling size() every loop
  218. for (int i = 0; i < list_size; i++) {
  219. if (integer.compareTo(list.get(i)) >= 0) {
  220. list.add(i, integer);
  221. break;
  222. }
  223. }
  224. }
  225. }
  226.  
  227. private static void linearInsertionToDynamicArray(Integer[] numbers, DynamicIntArray array) {
  228. for(Integer integer : numbers){
  229. int value = integer.intValue();
  230. // int array_size = array.size(); // on purpose: even faster would be to avoid calling size() every loop
  231. for(int idx = 0; idx < array.size(); idx++){
  232. if(value >= array.get(idx)){
  233. array.insertAt(idx, value);
  234. break;
  235. }
  236. }
  237. }
  238. }
  239.  
  240. }
Success #stdin #stdout 8.23s 245824KB
stdin
Standard input is empty
stdout
#Elements       LinkedList           ArrayList            DynamicArray        
100             47         (157%)    39         (130%)    30         (100%)
200             177        (197%)    128        (142%)    90         (100%)
500             1074       (205%)    802        (153%)    524        (100%)
1000            4527       (233%)    2756       (142%)    1946       (100%)
2000            21782      (259%)    10873      (129%)    8405       (100%)
3000            49707      (232%)    26284      (122%)    21468      (100%)
4000            91929      (238%)    46914      (121%)    38652      (100%)
5000            141390     (246%)    75871      (132%)    57452      (100%)
10000           628813     (258%)    317474     (130%)    243352     (100%)
20000           3125540    (322%)    1319927    (136%)    971471     (100%)