What is the best data structure for representing an upper triangular matrix in Java?

Question

Suppose an upper triangular matrix of integers is given. What's the best way of storing this in Java? The naive 2d int array is obviously not efficient. The solution I came up with was moved to the answers section.

Answer 1

If you want to save memory, your solution looks great - it's called a packed storage matrix. Column by column, top down, your array would look like this: 1 2 6 3 7 8 4 1 9 5

I would suggest a simpler calculation of your indices, based on the sum formula (n² + n) / 2 (row and column is zero based).

list_index = (column^2 + column) / 2 + row;

An implementation could look like the following:

public class TriangularMatrix {
    private final int[] list;

    public TriangularMatrix(int size) {
        list = new int[sumFormula(size)];
    }

    public int set(int row, int column, int value) {
        validateArguments(row, column);

        int listIndex = getListIndex(row, column);
        int oldValue = list[listIndex];
        list[listIndex] = value;

        return oldValue;
    }

    public int get(int row, int column) {
        validateArguments(row, column);

        return list[getListIndex(row, column)];
    }

    private void validateArguments(int row, int column) {
        if (row > column) {
            throw new IllegalArgumentException("Row (" + row + " given) has to be smaller or equal than column (" + column + " given)!");
        }
    }

    private int getListIndex(int row, int column) {
        return sumFormula(column) + row;
    }

    private int sumFormula(int i) {
        return (i*i + i) / 2;
    }
}

There is another question on SO discussing the (negative) performance impact, although it's about Fortran.

Answer 2

What about Guava's Table? It is implemented using HashMaps or TreeMaps (as well as 2D array if required), but it offers much nicer API than defining a Map<Integer, Map<Integer, V>>.