fork download
copy 
  1. /*
  2. Code example used in blog-article: "Java Battle Royal: LinkedList vs ArrayList vs DynamicIntArray"
  3. http://k...content-available-to-author-only...s.com/2012/08/08/java-galore-linkedlist-vs-arraylist-vs-dynamicintarray/
  4.  
  5. Comparing ArrayList, DynamicIntArray, LinkedList
  6. Scope of code:
  7. [Number crunching example that should favmour the linked list]
  8. [...] filter a collection of elements, removing the values that are above or below a threshold. This "should" be perfect for an linked list ... but it is shown here that it can with just a barely better approach then the naive approach will still beat the LinkedList 
  9.  
  10. See the article for explanation
  11. */
  12. import java.util.ArrayList;
  13. import java.util.Arrays;
  14. import java.util.Iterator;
  15. import java.util.LinkedList;
  16. import java.util.Random;
  17. import java.util.List;
  18.  
  19. public class Main {
  20.  
  21. class DynamicIntArray {
  22.  
  23.   private int[] storage;
  24.   private int size;
  25.   private final  int INITIAL_CAPACITY = 8;
  26.   private final int GROW_FACTOR = 2;
  27.  
  28.   private void rangeCheck(int index){
  29.     if(index < 0 || index >= size) 
  30.       throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
  31.   }  
  32.  
  33.   // ref: http://w...content-available-to-author-only...t.net/Data_structures/Dynamic_array/Capacity_management
  34.   private void ensureCapacity(int size_wanted) {
  35.     int max_capacity = storage.length;
  36.     if (size_wanted > max_capacity) {
  37.       max_capacity = max_capacity * GROW_FACTOR +1; 
  38.       // http://d...content-available-to-author-only...e.com/javase/6/docs/api/java/util/Arrays.html#copyOf%28int[],%20int%29
  39.       storage = Arrays.copyOf(storage, max_capacity); // increases array size + copy contents
  40.     } 
  41.  }
  42.  
  43.  
  44.  public DynamicIntArray() {
  45.     storage = new int[INITIAL_CAPACITY]; 
  46.     size = 0;
  47.   }
  48.  
  49.  public DynamicIntArray(int capacity) {
  50.     storage = new int[capacity]; 
  51.     size = 0;
  52.   }
  53.  
  54.  
  55.    public int size() {return size;}
  56.  
  57.    public boolean equals(List<Integer> list)
  58.    {
  59.      boolean success = (list.size() == size());
  60.      if(success) {
  61.        for(int idx = 0; success && (idx < size()); ++idx) {
  62.          success = success && (get(idx) == list.get(idx).intValue());
  63.        }
  64.      }
  65.      return success;
  66.    } 
  67.  
  68.  
  69.     public int get(int position){
  70.     rangeCheck(position);
  71.     return storage[position];
  72.   }
  73.  
  74.     public void set(int index, int value){
  75.       rangeCheck(index);
  76.       storage[index] = value;
  77.     }
  78.  
  79.     public void add(int value) { 
  80.       insertAt(size, value);  // same as c++ std::vector push_back
  81.     }
  82.  
  83.  
  84.     // Insert the value at the given index and shift 'tail' to give space.
  85.     // The value can either be last position (size) or within the range 0 -> size.
  86.     public void insertAt(int index, int value) {
  87.       if(index < 0 || index > size)    // allows for push_back to last index also
  88.         throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
  89.  
  90.       ensureCapacity(size+1);
  91.       int move_count = size - index;                                    // number of elements to shift
  92.       if( move_count > 0)                                       
  93.         System.arraycopy(storage, index, storage, index+1, move_count);
  94.  
  95.        storage[index] = value;
  96.        size++;
  97.     }
  98.  
  99.       public void removeAt(int index) {
  100.         rangeCheck(index);
  101.         int move_count = size - index - 1;
  102.        if (move_count > 0)
  103.           System.arraycopy(storage, index + 1, storage, index, move_count);
  104.  
  105.        size--;
  106.       }
  107.  
  108.  
  109.     public void printAll() {
  110.       for (int idx = 0; idx < size; idx++)
  111.         System.out.printf("  [%d]=%d", idx, get(idx));
  112.  
  113.       System.out.println();
  114.    }
  115. } // DynamicIntArray
  116.  
  117.  
  118.     // Measuring filtering/remove of too large values
  119.     public static void main(String[] args) throws Exception {
  120.  
  121.         //Get the jvm heap size.
  122.         //long heapSize = Runtime.getRuntime().totalMemory();        
  123.         //Print the jvm heap size.
  124.         //System.out.println("Heap Size = " + heapSize);
  125.  
  126.      Main obj = new Main(); 
  127.     System.out.println("NO WARMUP: Repeating the same 'number-of-elements' changes the timing result");
  128.     System.out.println("   just a nice 'present' for using java\n\n");
  129.  
  130.     System.out.println("\n\n**************************");
  131.     obj.performanceOfFilter(10);
  132.     obj.performanceOfFilter(1000);
  133.     obj.performanceOfFilter(100000);
  134.   }
  135.  
  136.  
  137.      public void performanceOfFilter(int numbers) {
  138.         System.out.println("Filter containers with random " + numbers + " numbers");
  139.         System.out.println("Performance is measured in microseconds [us]\n");
  140.  
  141.         Integer[] array = new Integer[numbers];
  142.         Random random = new Random();
  143.         DynamicIntArray    dynamicArray = new DynamicIntArray();
  144.  
  145.         for (int i = 0; i < array.length; i++)
  146.         {
  147.            int value = random.nextInt(Integer.MAX_VALUE);
  148.            array[i] = value;
  149.            dynamicArray.add(value);
  150.         }
  151.  
  152.  
  153.         LinkedList<Integer> linkedList = new LinkedList<Integer>(Arrays.asList(array));
  154.         ArrayList<Integer> arrayListNaive = new ArrayList<Integer>(Arrays.asList(array));
  155.         ArrayList<Integer> arrayListLessNaive= new ArrayList<Integer>(Arrays.asList(array));
  156.         ArrayList<Integer> arrayListSmart = new ArrayList<Integer>(Arrays.asList(array));
  157.         ArrayList<Integer> arrayListSmartReplace= new ArrayList<Integer>(Arrays.asList(array));
  158.  
  159.  
  160.        /** ArrayList : Naive. Working against the natural direction of the array. 
  161.                       Lots of unnecessary shifting */
  162.         long before = System.nanoTime();
  163.         for (int i = 0; i < arrayListNaive.size(); i++)
  164.             if (arrayListNaive.get(i) > Integer.MAX_VALUE / 2)
  165.                 arrayListNaive.remove(i--);
  166.         System.out.println("Naive ArrayList \t\t" +(System.nanoTime() - before) / 1000);
  167.  
  168.  
  169.  
  170.        /** ArrayList : Less naive. Working with filtering in the 'direction of growth'
  171.                     i.e. some 'shuffling' can be avoided */
  172.         before = System.nanoTime();
  173.         for (int i = arrayListLessNaive.size() -1; i >= 0; i--)
  174.            if (arrayListLessNaive.get(i) > Integer.MAX_VALUE / 2)
  175.                 arrayListLessNaive.remove(i);
  176.         System.out.println("Less naive ArrayList \t\t" +(System.nanoTime() - before) / 1000);
  177.  
  178.  
  179.  
  180.         /** ArrayList: From David, suggesting a smart algorithm where set (replace) is used before trimming.
  181.                        The small enough items are set after each other at the front.
  182.                        Larger items or 'copies' at the end are removed by trimming */
  183.          before = System.nanoTime();
  184.          int insert = 0;
  185.          for (int i = 0; i < arrayListSmartReplace.size(); i++){
  186.           if (arrayListSmartReplace.get(i) <= Integer.MAX_VALUE / 2){  // small enough items are kept;
  187.             arrayListSmartReplace.set(insert, arrayListSmartReplace.get(i)); // replace 
  188.             insert++;
  189.           } 
  190.          } 
  191.          while (arrayListSmartReplace.size() > insert)  // trim/filter according to count
  192.           arrayListSmartReplace.remove(arrayListSmartReplace.size() - 1);
  193.         System.out.println("Davids 'set/replace' ArrayList \t" + (System.nanoTime() - before) / 1000);
  194.  
  195.  
  196.  
  197.         /** Linked-List: Very fast in this scenario. It is cache unfriendly, but avoids the shuffling intensive
  198.                          operations that the 'array' structures use */
  199.         before = System.nanoTime();
  200.         for (Iterator<Integer> it = linkedList.iterator(); it.hasNext(); )
  201.             if (it.next() > Integer.MAX_VALUE / 2)
  202.                 it.remove();
  203.         System.out.println("LinkedList \t\t\t"+ (System.nanoTime() - before) / 1000);
  204.  
  205.  
  206.         /**  ArrayList : Smart. Avoiding unnecessary shuffling by using a "work copy" */
  207.         before = System.nanoTime();
  208.         ArrayList arraylist_workcopy= new ArrayList(arrayListSmart.size()); // pre-allocating work copy makes sense
  209.         for (int i = 0; i < arrayListSmart.size(); i++) 
  210.             if (arrayListSmart.get(i) <= Integer.MAX_VALUE / 2)
  211.                 arraylist_workcopy.add(arrayListSmart.get(i));
  212.         System.out.println("Smart ArrayList\t\t\t" +(System.nanoTime() - before) / 1000);
  213.  
  214.  
  215.  
  216.         /** DynamicIntArray "smarter" (cache friendly) and uses a pre-allocated work copy */
  217.         before = System.nanoTime();
  218.         DynamicIntArray dynamic_workcopy= new DynamicIntArray(dynamicArray.size()); 
  219.         for (int i = 0; i < dynamicArray.size(); i++){
  220.             if (dynamicArray.get(i) <= (Integer.MAX_VALUE / 2))
  221.                 dynamic_workcopy.add(dynamicArray.get(i));
  222.         }
  223.         System.out.println("Smart DynamicIntArray \t\t" + (System.nanoTime() - before) / 1000); 
  224.  
  225.  
  226.  
  227.         boolean all_equal =  arrayListNaive.equals(linkedList) && 
  228.                              arrayListLessNaive.equals(arrayListNaive) &&
  229.                              arrayListSmartReplace.equals(arrayListLessNaive) &&
  230.                              arraylist_workcopy.equals(arrayListSmartReplace) && 
  231.                              dynamic_workcopy.equals(arrayListNaive);
  232.         System.out.println("All containers filtered equally: " + all_equal);
  233.         System.out.println("**************************************\n\n\n");
  234.     }
  235. }
Success #stdin #stdout 3.33s 246528KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
NO WARMUP: Repeating the same 'number-of-elements' changes the timing result
   just a nice 'present' for using java




**************************
Filter containers with random 10 numbers
Performance is measured in microseconds [us]

Naive ArrayList 		37
Less naive ArrayList 		14
Davids 'set/replace' ArrayList 	25
LinkedList 			140
Smart ArrayList			32
Smart DynamicIntArray 		26
All containers filtered equally: true
**************************************



Filter containers with random 1000 numbers
Performance is measured in microseconds [us]

Naive ArrayList 		1146
Less naive ArrayList 		640
Davids 'set/replace' ArrayList 	390
LinkedList 			1114
Smart ArrayList			293
Smart DynamicIntArray 		2458
All containers filtered equally: true
**************************************



Filter containers with random 100000 numbers
Performance is measured in microseconds [us]

Naive ArrayList 		2141932
Less naive ArrayList 		1035158
Davids 'set/replace' ArrayList 	3520
LinkedList 			5508
Smart ArrayList			3475
Smart DynamicIntArray 		2356
All containers filtered equally: true
**************************************
https://ideone.com/NH6jl
language:
Java (HotSpot 12)
created:
11 years ago
visibility:
secret

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!