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

Question

Suppose you are given an upper triangular matrix of integers. What is the best way to save this in Java? The naive 2d int array is clearly inefficient. The solution I came up with has been moved to the answer section.

Answer 1

I think I found a solution. Here is my solution: suppose you have an upper 4X4 triangular matrix.

1 2 3 4 0 6 7 1 0 0 8 9 0 0 0 5 

If you can match each element of M in a 1d array, this is the best solution. All you need to know is to know which row [row, col] matches that element of your 1d array. Here's how you do magic:

 start_index=((col_index-1)+1)+((col_index-2)+1)+...+1 end_index=start_index + col_index 

For example: if I want to find where the elements are in the third column of the matrix, in an array:

 start_index=((3-1)+1)+((3-2)+1)+((3-3)+1)=6 end_index=6+3=9 

So, all I have to do is start at index 6 of my array and read all the elements up to index 9 (including the 9th element). Following this procedure, you can store and retrieve all cells of the matrix nXn in the space (n + n ^ 2) / 2.

Answer 2

How about a guava Table ? It is implemented using HashMaps or TreeMaps (as well as a 2D array, if required), but it offers a much more convenient API than the definition of Map<Integer, Map<Integer, V>> .

Answer 3

If you want to save memory, your solution looks great - it is called a packed storage matrix . Column by column, from top to bottom, your array will 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 are based on zero value).

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

The implementation may look like this:

 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 about SO that discusses the (negative) impact of performance, although this applies to Fortran.

Answer 4

If the matrix is ​​always diagonal, I would use:

 List<List<Integer>> matrix = ... 

If this is a sparse matrix, I would use maps:

 Map<Map<Integer>> = ... 

In this second case, you may need to wrap the map in a class using get and set operations to control access to new rows and columns.

All this, however, depends on your needs, memory limitations and matrix size.