fork(2) download
copy 
  1. import java.util.ArrayList;
  2. import java.util.Arrays;
  3. import java.util.List;
  4. import java.util.Random;
  5.  
  6. public class Main {
  7.  
  8.     static class Result {
  9.  
  10.         int size;
  11.         long listTime;
  12.         long arrayListTime;
  13.  
  14.         public Result(int size) {
  15.             this.size = size;
  16.         }
  17.     }
  18.  
  19.     public static void main(String[] args) throws Exception {
  20.  
  21.         // warm up code to make the benchmark more accurate
  22.         for (int i = 0; i < 100; i++) {
  23.             listVsArrayListLinearPerformance(1000);
  24.         }
  25.  
  26.         // print the header
  27.         System.out.printf("%-15s %-20s %-20s%n",
  28.                 "#Elements", "ArrayList", "List");
  29.  
  30.         // perform the benchmarking
  31.         printResult(listVsArrayListLinearPerformance(1000));
  32.         printResult(listVsArrayListLinearPerformance(2000));
  33.         printResult(listVsArrayListLinearPerformance(3000));
  34.         printResult(listVsArrayListLinearPerformance(4000));
  35.         printResult(listVsArrayListLinearPerformance(5000));
  36.         printResult(listVsArrayListLinearPerformance(10000));
  37.         printResult(listVsArrayListLinearPerformance(20000));
  38.     }
  39.  
  40.     private static void printResult(Result r) {
  41.  
  42.         long min = Math.min(r.listTime, r.arrayListTime);
  43.  
  44.         System.out.printf("%-15d %-10d (%-3.0f%%)    %-10d (%-3.0f%%)%n",
  45.                 r.size,
  46.                 r.arrayListTime, (100 * (double) r.arrayListTime) / min,
  47.                 r.listTime, (100 * (double) r.listTime) / min);
  48.     }
  49.  
  50.     private static Result listVsArrayListLinearPerformance(int size) {
  51.  
  52.         Integer[] array1 = new Integer[size];
  53.         Integer[] array2 = new Integer[size];
  54.         Random random = new Random(123456789L);
  55.  
  56.         ArrayList<Integer> simpleList = new ArrayList<>(Arrays.asList(-1));
  57.         ArrayList<Integer> arrayList = new ArrayList<>(Arrays.asList(-1));
  58.  
  59.         for (int i = 0; i < size; i++) {
  60.             array1[i] = random.nextInt(Integer.MAX_VALUE);
  61.             array2[i] = random.nextInt(Integer.MAX_VALUE);
  62.         }
  63.  
  64.         Result result = new Result(size);
  65.  
  66.         long before;
  67.  
  68.         before = System.nanoTime();
  69.         linearInsertionAsList(array1, simpleList);
  70.         result.listTime = (System.nanoTime() - before) / 1000;
  71.  
  72.         before = System.nanoTime();
  73.         linearInsertionAsArrayList(array2, arrayList);
  74.         result.arrayListTime = (System.nanoTime() - before) / 1000;
  75.  
  76.         return result;
  77.     }
  78.  
  79.     private static void linearInsertionAsList(Integer[] intArray, List<Integer> list) {
  80.         for (Integer integer : intArray) {
  81.             int list_size = list.size(); // avoid calculating the size every time
  82.             for (int i = 0; i < list_size; i++) {
  83.                 if (integer.compareTo(list.get(i)) >= 0) {
  84.                     list.add(i, integer);
  85.                     break;
  86.                 }
  87.             }
  88.         }
  89.     }
  90.  
  91.     private static void linearInsertionAsArrayList(Integer[] intArray, ArrayList<Integer> list) {
  92.         for (Integer integer : intArray) {
  93.             int list_size = list.size(); // avoid calculating the size every time
  94.             for (int i = 0; i < list_size; i++) {
  95.                 if (integer.compareTo(list.get(i)) >= 0) {
  96.                     list.add(i, integer);
  97.                     break;
  98.                 }
  99.             }
  100.         }
  101.     }
  102. }
Success #stdin #stdout 4.38s 380352KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
#Elements       ArrayList            List                
1000            1558       (100%)    2704       (174%)
2000            6303       (100%)    11117      (176%)
3000            16133      (100%)    25759      (160%)
4000            28265      (100%)    47546      (168%)
5000            42943      (100%)    77693      (181%)
10000           191791     (100%)    318407     (166%)
20000           1257679    (100%)    1789171    (142%)
https://ideone.com/U58ZA8
language:
Java (12.0.1)
created:
10 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!