12

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

Community
  • 1
  • 1
Nope
  • 34,682
  • 42
  • 94
  • 119
  • 1
    Implementation of a 2D array depends on the language. You can get some good answers here: http://stackoverflow.com/questions/732684/implementing-a-matrix-which-is-more-efficient-using-an-array-of-arrays-2d-or and here: http://stackoverflow.com/questions/1242705/performance-of-2-dimensional-array-vs-1-dimensional-array – Robert Cartaino Sep 19 '09 at 22:51

5 Answers5

36

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 .

ldog
  • 11,707
  • 10
  • 54
  • 70
  • Again, that's not the question. – Joren Sep 19 '09 at 23:09
  • 1
    +1 for such a great response! I know this is [many] years old, but still a very valuable piece of information. Thanks, @ldog – rodrigo-silveira Sep 01 '13 at 02:41
  • Great answer. Once you have y, you can get x via "x = i - (W * y)" instead of i % W or (i & (W-1)). So if width not a power of 2, the worst case is a single division to find y. In the case where width is a power of 2, getting x is a toss-up between a multiplication and a bitwise AND.... I don't know which is faster, but they're both very fast. – Ph0t0n Aug 22 '22 at 07:34
3

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.

Joren
  • 14,472
  • 3
  • 50
  • 54
3

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

Community
  • 1
  • 1
Alex Reynolds
  • 95,983
  • 54
  • 240
  • 345
2

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.

sepp2k
  • 363,768
  • 54
  • 674
  • 675
2
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.

codymanix
  • 28,510
  • 21
  • 92
  • 151