ArrayList vs Doubling Array Size?

Question

So a common programming practice for when an array can't hold the amount of information we want it to, is to double the size of an array. We do this by creating a new array, with double the original arrays size, populating this new array with the old values, and setting it as the old array. Here's a example in Java:

public int[] doubleArray(int[] old) {
    int[] doubled = new int[old.length * 2];
    for (int i = 0; i < old.length; i++) {
        doubled[i] = old[i];
    }
    return doubled;
}

So is it more better to use a standard array and double the size, when needed, or to simply use an ArrayList (which changes its own size based on the input you give it by 1)? Basically, is it better to double an arrays size when you need to store more than the array allows, or to increase its size by 1 each time? And what would be the limit to which one becomes a better choice than the other?

If I had to guess, using a standard array should be faster, given that it's in the java.lang, so I made the following class to test my theory:

public class ArrayTesting {
    public static void main(String[] args) {
    long startTime1 = System.nanoTime();
    int[] ints = new int[10];
    for (int i = 0; i < ints.length; i++) {
      ints[i] = i * 2;
    }
    long timeToSetOriginalValues = (System.nanoTime() - startTime1);
    long startTime2 = System.nanoTime();
    ints = doubleArray(ints);
    long timeToDouble = (System.nanoTime() - startTime2);
    long startTime3 = System.nanoTime();
    for (int i = 9; i < ints.length; i++) {
      ints[i] = i * 2;
    }
    long timeToSetNewValues = (System.nanoTime() - startTime3);
    System.out.println("Set Values in " + timeToSetOriginalValues);
    System.out.println("Doubled Array in " + timeToDouble);
    System.out.println("Finished setting values in " + timeToSetNewValues);
    System.out.println("Total time: " + (timeToSetOriginalValues + timeToDouble + timeToSetNewValues));
  }

  public static int[] doubleArray(int[] old) {
    int[] doubled = new int[old.length * 2];
    for (int i = 0; i < old.length; i++) {
      doubled[i] = old[i];
    }
    return doubled;
  }
}

But for an unknown reason, I am getting extremely varying results. Varying total time from everything between 11,000 and 4,000. Assuming it's something I did wrong, is there someone better at timing who could answer my question?

Answer 1

Right well I looked into it and here are the results:

I created a new classes for testing the time in editing an array, and the time in editing an ArrayList. Let's start with the ArrayTesting class.

public class ArrayTesting {
    private static long totalTotal = 0L;
    private static int[] ints = new int[10];
    public static void main(String[] args) {
        for (int i = 0; i < 5; i++) {
            runTest();
        }
        System.out.println("Final Length of Array: " + ints.length);
        System.out.println("Total Time was: " + totalTotal);
    }
    private static void runTest() {
        long startTime = System.nanoTime();
        for (int i = 0; i < ints.length; i++) {
            ints[i] = i * 2;
        }
        ints = doubleArray(ints);
        for (int i = 9; i < ints.length; i++) {
            ints[i] = i * 2;
        }
        long testTime = System.nanoTime() - startTime;
        totalTotal = totalTotal + testTime;
    }

    private static int[] doubleArray(int[] old) {
        int[] doubled = new int[old.length * 2];
        for (int i = 0; i < old.length; i++) {
            doubled[i] = old[i];
        }
        return doubled;
     }
}

The process for this class is as follows:

1. Create new Array of Integer Objects (yes this matters), length 10.

2. For five iterations, set all the indexes of the current array to index * 2, then double the array size, and fill the new indexes with their respective values of index * 2.

3. Print results

Following the same process, I then created a testing class for an ArrayList:

import java.util.ArrayList;
class ArrayListTester {
    public static ArrayList<Integer> arl = new ArrayList<Integer>();
    public static long totalTotal = 0L;
    public static void main(String[] args) {
        //Set initial size for ArrayList to 10
        while(arl.size() < 10) arl.add(0);
        //Setting the size was not timed.
        for (int i = 0; i < 5; i++) {
            runTest();
        }
        System.out.println("Total ArrayList size: " + arl.size());
        System.out.println("Total Time: " + totalTotal);
    }
    public static void runTest() {
        long startTime1 = System.nanoTime();
        int initialSize = arl.size();
        for (int i = 0; i < initialSize * 2; i++) {
            if (i < initialSize)
                arl.set(i, ((Integer) i * 2));
            else
                arl.add((Integer) i * 2);
        }
        long totalForRun = System.nanoTime() - startTime1;
        totalTotal = totalTotal + totalForRun;
    }
}

If you read through this class, you will indeed find it follows the same steps, however using an ArrayList allows the code to be much more consise.

So now let's get to our results..

Since each class runs the doubling size thing for 5 iterations, our array size for both at the end is 320 or 10 * (2 ^ 5) (note the starting size for both arrays is 10). However, after a few quick runs of the test, the time consumption is drastically different.

Now, running the ArrayTester class 5 times in a row, and taking the average time for each run (adding it up and dividing by the number of runs) I recieved an average of 468,290 nanoseconds, some of you may be thinking this is a pretty decent chunk for simply doubling an array, but just you wait...

Next, moving to the ArrayListTester class and running it the same 5 times to gain an average, I received an average of exactly 2,069,230 nanoseconds.

If you'd like to test out these numbers for yourself, I ran these programs on an online compiler/interpreter here.

Final Result: It took the ArrayList almost 4.5 times longer to complete the same task.

Now going back to the original question asked: "So is it better to use a standard array and double the size, when needed, or to simply use an ArrayList?"

The answer truly deals with how efficient you want your code to be. For an ArrayList, efficiency literally doesn't exist anymore, however the aesthetics and organization of the code are dramatically increased. On the other hand, if you are looking for a more efficient method of handling things, and don't care as much about the code you need to write, then use an Array.

Answer 2

If you look at the ArrayList implementation, even it has the Array object, and when you call add method, it will also ensures the capacity and if needed, increments the size of the array like

elementData = Arrays.copyOf(elementData, newCapacity); 

Where elementData is the internal array to store the data.

Regarding Performance or memory consumption, since it is a wrapper with many functionality, obviously there will be some cost compare to the Array object.

Answer 3

An simple Array will always be faster, because ArrayList is an Array that creates a new Array when it is out of space and shrinks it when it is to big.

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

Code is taken from the OpenJDK7 here you can clearly see, the small overhead a simply add method would have, which is checking the size of the array if it is to small or to big, copy the array to an array with a bigger size and then set the element. An normal Array would just have.

Arr[index] = value;

But the increased functionality of ArrayLists and the improvements of your code quality, will in most non performance optimised scenarios be far superior, to an traditional Array.

As research you can find examples of very well implemented resizing Arrays at http://algs4.cs.princeton.edu/home/, with a example of a resizing Array http://algs4.cs.princeton.edu/13stacks/ResizingArrayStack.java.html.