Representing a 2D array as a 1D array [duplicate]

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

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 most likely miss this micro-optimization so you'd have to implement it yourself.

Modulus is a slow operator in C/C++, so making it disappear is advantageous.

Also, with large 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 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_order .

Answer 2

Take a look at Performance of 2-dimensional array vs 1-dimensional array