Representing a 2D array as a 1D array

Question

Possible Duplicates:
Implementing a matrix, which is more efficient - using an Array of Arrays (2D) or a 1D array?
Performance of 2-dimensional array vs 1-dimensional array

I was looking at one of my buddy's molecular dynamics code bases the other day and he had represented some 2D data as a 1D array. So rather than having to use two indexes he only has to keep track of one but a little math is done to figure out what position it would be in if it were 2D. So in the case of this 2D array:

two_D = [[0, 1, 2],
         [3, 4, 5]]

It would be represented as:

one_D = [0, 1, 2, 3, 4, 5]

If he needed to know what was in position (1,1) of the 2D array he would do some simple algebra and get 4.

Is there any performance boost gained by using a 1D array rather than a 2D array. The data in the arrays can be called millions of times during the computation.

I hope the explanation of the data structure is clear...if not let me know and I'll try to explain it better.

Thank you :)

EDIT The language is C

Answer 1

Often 2D arrays are implemented as 1D arrays. Sometimes 2D arrays are implemented by a 1D array of pointers to 1D arrays. The first case obviously has no performance penalty compared to a 1D array, because it is identical to a 1D array. The second case might have a slight performance penalty due to the extra indirection (and additional subtle effects like decreased cache locality).

It's different for each system what kind is used, so without information about what you're using there's really no way to be sure. I'd advise to just test the performance if it's really important to you. And if the performance isn't that important, then don't worry about it.

For C, 2D arrays are 1D arrays with syntactic sugar, so the performance is identical.

Answer 2

Take a look at http://stackoverflow.com/questions/1242705/performance-of-2-dimensional-array-vs-1-dimensional-array

Answer 3

You didn't mention which language this is regarding or how the 2D array would be implemented. In C 2D arrays are actually implemented as 1D arrays where C automatically performs the arithmetic on the indices to acces the right element. So it would do what your friend does anyway behind the scenes.

In other languages a 2d array might be an array of pointers to the inner arrays, in which case accessing an element would be array lookup + pointer dereference + array lookup, which is probably slower than the index arithmetic, though it would not be worth optimizing unless you know that this is a bottleneck.

Answer 4

oneD_index = 3 * y + x;

Where x is the position within the row and y the position in the column. Instead of 3 you use your column width. This way you can convert your 2D coordinates to a 1D coordinate.

Answer 5

For a 2-d Array of width W and height H you can represent it as a 1-d Array of length W*H where each index

 (x,y)

where x is the column and y is the row, of the 2-d array is mapped to to the index

i=y*W + x

in the 1-D array. Similarily you can use the inverse mapping:

y = i / W
x = i % W

. If you make W a power of 2 (W=2^m), you can use the hack

y = i >> m;
x = (i & (W-1))

where this optimization is restricted only to the case where W is a power of 2. A compiler would miss this optimization so you'd have to implement it yourself.

Other than that I don't think there is a big advantage in the normal case.

edit ---

modulus is the slowest operator by far in C/C++, so making it disappear is a huge advantage. I've used this trick several times in my code and its worth remembering.

Also, with huge 2-d arrays keep in mind that the computer stores them in memory as a 1-d array and basically figures out the indexes using the mappings I listed above.

Far more important than the way that you determine these mappings is how the array is accessed. There are two ways to do it, column major and row major. The way that you traverse is far far more important than any other factor because it determines if you are using caching to your advantage. Please read http://en.wikipedia.org/wiki/Row-major%5Forder .