Implementing a matrix, which is more efficient - using an Array of Arrays (2D) or a 1D array?

Question

When implementing a Matrix construct using arrays, which would be more efficient? Using a 1D array, or an array of arrays (2D)?

I would think a 2D is more efficient as you already have the X and Y coordinates of an element, where in a 1D implementation you have to calculate the index.

Edit: it is being implemented using Java

Answer 1

"Efficient" is not a catch-all term.

An array-of-arrays solution is more efficient in terms of storage, where the array may be sparse (i.e., you can use null pointer to represent a matrix line of all zeroes). This would be (in C):

int *x[9];

where each "int *" would be allocated separately.

A 2D array (which is not necessarily an array of arrays) will generally be faster (efficient in terms of speed) since it works out memory locations with math, without having to de-reference memory locations. I'm talking of the construct:

int x[9][9];

A 1D array of the form:

int x[81];

is unlikely to be any faster than the equivalent 2D version since you still have to do the calculations at some point to find the correct cell (manually in your code rather than letting the compiler do it).

After edit where Java was added as a requirement:

I believe Java 2D arrays are of the array of arrays variety (which will require two memory accesses as opposed to the one required for a 1D array) so the 1D array with manual index calculation may well be faster. So, instead of declaring and using:

int x[width][height];
x[a][b] = 2;

you may get more speed with:

int x[width*height];
x[a*height+b] = 2;

You just need to be careful that you don't get the formula mixed up anywhere (i.e., don't swap 4 and 7 inadvertently).

This speed difference is based on how I think Java is coded under the covers so I could be wrong (but I doubt it :-). My advice is, as always for optimisation questions, measure, don't guess!

Answer 2

I'm going to break ranks with the answers to date and suggest the following reason that a 1D array is quite possibly faster.

A 2D array involves 2 memory accesses. A[x][y] for instance first must lookup A[x], and then do another lookup of that array[y].

A 1D implementation traditionally would be A[x + (width *y)]. When width is in registers (or a literal), this means 2 math ops and 1 lookup instead of 2 lookups. Lookups are orders of magnitude slower than math ops, so if width is in register even a small percent of the time, or is a literal, it will be faster.

Of course the standard caveats apply. Always profile, and avoid premature optimizations.