List<List<String>> vs. String[][]

Question

I'm looking to create a 2D String 'matrix' object in Java. My two goals with this are for efficiency and code simplicity.

I've heard that using an ArrayList is quite a bit more efficient than a String[][]. Firstly, I'm wondering if that's true, and if so, how much more efficient?

The other thing is that I must have the ability to add columns and rows to the 'matrix'. I was able to develop some efficient algorithms for adding rows and columns to a String[][]. I'm curious to know if it would be worth it to develop algorithms to manipulate a 2D List in this way - would there be a significant performance improvement?

Thanks for your help!

Answer 1

List is an interface. Given this interface, you can use different implementation such as ArrayList, LinkedList, CopyOnWriteArrayList, etc

So your question perhaps should be rephrased as

ArrayList<ArrayList<String>> vs String[][]

ArrayList is a list implemented using an array. It has methods that let you handle element in a specific position:

void add(int index, E element);
E    get(int index);

I used to think ArrayList is almost as fast as an array, but I guess the actual usage would determine the actual performance difference. Below I add some results from an anecdotal experiment that shows that array is faster than ArrayList, especially during the population of the 2-D matrix. The access times of the two seem to be on par with each other.

ArrayList gives you some advantage, such as you don't have to know the size in advance. Having that said, however, if I am sure that what I need is an array and never a generic list (for example, as you said, for matrix computation), then I may use an array for the more succinct syntax.

String s1 = array[i][j];
array[i][j] = s1;

Versus

String s2 = list.get(j).get(i);
list.get(j).add(i, s2);

For more information distinguishing the interface from its implementation, you can refer to this tutorial by Oracle/Sun:

https://docs.oracle.com/javase/tutorial/collections/implementations/list.html

Anecdotal Experiment

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class ArrayListVsString {

    private static final int NUM_TESTS = 5;

    public static void main(String[] args) {
        List<List<String>>  list;
        String[][]          array; 
        int height  = 500;
        int width   = 1000;
        String __ = "    "; // indent
        for (int n=0; n<NUM_TESTS; n++) {
            System.out.format("Testing 2D matrix of %dx%d: Test %d%n"
                    , height, width, n);
            /*
             * Time to populate the matrices
             */
            long startTime = System.nanoTime();
            // array
            String subTestArray = "2-D array";
            array = new String[width][height];
            for (int i=0; i<width; i++) {
                for (int j=0; j<height; j++) {
                    array[i][j] = getRandomString();
                }
            }
            startTime 
                = logElapsedTime(startTime
                                , __ + "creating matrix as " 
                                     + subTestArray);
            // array-list
            String subTestList = "2-D array-list";
            list = new ArrayList<>(height);
            for (int j=0; j<height; j++) {
                List<String> row = new ArrayList<>(width);
                list.add(j, row);
                for (int i=0; i<width; i++) {
                    String element = getRandomString();
                    list.get(j).add(i, element);
                }
            }
            startTime 
                = logElapsedTime(startTime
                            , __ + "creating matrix as " 
                                 + subTestList);

            int hash = 0;
            /*
             * Time to do a full walk through all the elements
             */
            // array
            for (int i=0; i<width; i++) {
                for (int j=0; j<height; j++) {
                    hash += (array[i][j]).hashCode();
                }
            }
            startTime 
                = logElapsedTime(startTime
                                , __ + "full walk of matrix as" 
                                     + subTestArray);

            // array-list
            for (int j=0; j<height; j++) {
                for (int i=0; i<width; i++) {
                    hash += list.get(j).get(i).hashCode();
                }
            }
            startTime 
                = logElapsedTime(startTime
                                , __ + "full walk of matrix as "
                                     + subTestList);
            list = null;

        }

    }

    private static Random random = new Random();

    private static String getRandomString() {
        return String.valueOf(random.nextInt());
    }

    private static long logElapsedTime(long startTimeNano
            , String action) {
        long elapsedTimeNano = System.nanoTime() - startTimeNano;
        System.out.format("%s took %,d ms%n"
                    , action, elapsedTimeNano/1000000);

        return System.nanoTime();
    }
}

Results

Testing 2D matrix of 500x1000: Test 0
    creating matrix as 2-D array took 117 ms
    creating matrix as 2-D array-list took 232 ms
    full walk of matrix as2-D array took 25 ms
    full walk of matrix as 2-D array-list took 31 ms
Testing 2D matrix of 500x1000: Test 1
    creating matrix as 2-D array took 65 ms
    creating matrix as 2-D array-list took 186 ms
    full walk of matrix as2-D array took 20 ms
    full walk of matrix as 2-D array-list took 30 ms
Testing 2D matrix of 500x1000: Test 2
    creating matrix as 2-D array took 61 ms
    creating matrix as 2-D array-list took 60 ms
    full walk of matrix as2-D array took 14 ms
    full walk of matrix as 2-D array-list took 15 ms
Testing 2D matrix of 500x1000: Test 3
    creating matrix as 2-D array took 66 ms
    creating matrix as 2-D array-list took 358 ms
    full walk of matrix as2-D array took 16 ms
    full walk of matrix as 2-D array-list took 15 ms
Testing 2D matrix of 500x1000: Test 4
    creating matrix as 2-D array took 45 ms
    creating matrix as 2-D array-list took 55 ms
    full walk of matrix as2-D array took 14 ms
    full walk of matrix as 2-D array-list took 15 ms

Answer 2

First the simple answer: Direct array operations will be faster since you avoid the overhead of the general purpose classes. You can even gain more performance by leveraging the Unsafe instance (non public API) for direct array access.

And for the opinion part: I would rather look at how things can be executed concurrently or distributed amongst different systems if performance is that important. In that case I would prefer avoiding using arrays directly since that would be hard to maintain. But of course it all depends on your specific use case.

So, like with all performance related questions, do some measurements for your specific use case and decide for yourself what works best for you.

And like I said in the comments, I have fiddled around with own Matrix implementation which have two specialised Map implementations (CompactArrayMap and DirectArrayMap) which are both int to key mappings on the keys natural order, so much like an array but with map functionality.