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
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