Friday, April 19, 2013

memory allocation for 2D array

the memory of a computer is linear and not a matrix like a 2D array. So, the elements of the array are stored either by row, called "row-major", or by column, called "column-major". Row-major order is used most notably in C and C++ during static declaration of arrays.
In C, since the length of each row is always known, the memory can be filled row one row at a time, one after the other.
Example:
a[i][j] =
1 2 3 4 5 6 7 8 9
Representation in the memory: In row-major: 1 2 3 4 5 6 7 8 9 In column-major: 1 4 7 2 5 8 3 6 9
Address calculation of an element:

Row-Major :
addr (i,j) = B + W * ( Nc * (i - Lr) + (j-Lc) )


Col-Major :
addr (i,j) = B + W * ( (i - Lr) + Nr * (j-Lc) )
i,j = subscript number. B = Base address W = width (size) of each element Nc = Number of Columns Nr = Number of Rows Lc = Lower-bound of Column Lr = Lower-bound of Row

In above example,
 for element (6), i.e., a(1,2) in row-major or a(2,1) in col-major, B = 200 (say) W = 2 Lr=Lc=0 Nc=Nr=3
addr (1,2) = 210; addr (2,1) = 210


                                                                   


Suppose element of array A[4][5] occupies 4 bytes, and the address of the 1st element is 49.  Find the address of the element A(4,3) when the storage is row major.

                                                     = BA + [n * (i - LBR) + (j - LBC)] * w
                                                     = 49 + [5 * (4 – 0) + (3 - 0)] * 4
                                                     = 49 + [23] * 4
                                                     = 49 + 92
                                                     = 141

No comments:

Post a Comment