fork(8) download
copy 
  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://i...content-available-to-author-only...e.com/lmNDj)
  7.  
  8. i.e. http://k...content-available-to-author-only...s.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://w...content-available-to-author-only...t.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://d...content-available-to-author-only...e.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://d...content-available-to-author-only...e.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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
#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%)
https://ideone.com/JOJ05
language:
Java (HotSpot 12)
created:
12 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!