ansaurus

Question

array offset calculations in multi dimensional array (column vs row major)

Answer 1

+2 A:

I would see the Row-major order Wikipedia article. There is a section that described dimensions higher than 2. There is also a good article here. That article gives the following formula for a three-dimensional array using a row-major layout:

Address = Base + ((depthindex*col_size+colindex) * row_size + rowindex) * Element_Size

For a 3D array: type A[depth] [col] [row]. The base is the starting offset of the array. In addition, the size variables are the different sizes of each dimension. The Element_Size variable denotes the size of whatever type the array is composed of.

Suppose you had row-major array a[4][6][5] composed of standard C++ integers. To compute the offset of a[1][3][2], you would plug the following numbers into the formula:

Address = Base + ((1 * 6 + 3) * 5 + 2) * 4

For a 3 dimensional array that has a column-major layout, the equation would rather be this:

Address = Base + ((rowindex*col_size+colindex) * depth_size + depthindex) * Element_Size

The numbers you would plug in for the example above using a column-major layout would now be this:

Address = Base + ((2 * 6 + 3) * 4 + 1) * 4

Cory Walker 2009-04-25 23:19:08

Aren't 3D arrays addressed by [col][row][depth] or [X][Y][Z]?

mrwes 2009-04-27 09:21:09

On further investigation it turns out that C treats 3D arrays as [depth][col][row]

mrwes 2009-04-27 19:28:52

Answer 2

+1 A:

The terms 'row major' and 'column major' don't translate well to a third dimention. The notion that the next element stored is from the current row or current column break down. It sounds a little comical but this becomes 'depth major' vs. 'width major' ordering. Each subsequent element is no longer a single entry but one full two dimentional matrix.

          / X
         / 
        +---+---+---+
       /   /   /   /|  
      +---+---+---+-+-------   
      | 1 | 5 | 9 |/|  Y
      +---+---+---+ +
      | 2 | 6 | A |/|
      +---+---+---+ +
      | 3 | 7 | B |/| 
      +---+---+---+ +
      | 4 | 8 | C |/
      +---+---+---+

So the memory would literally have 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 in memory sequentially. This is classical column major ordering. By placing the D entry at the position marked X you have not changed the fact that your matrix has colum major ordering. If you place the D entry where the Y is you still have not changed the fact that you are using column major ordering. Where you decide to place the next block will affect if you are using depth major (X) or width major (Y) ordering. As you well know these are equivalents but calling it something may assist you writing equations:

[ 0 Based arrays assumed ]

You access the memory location of a two dimentional colum major element through the equation:

MatrixOffset = base + (sizeof(entry) * ((4 * ( column - 1 ))   +  (row - 1)))

This address would be adjusted using depth or width its all a matter of terminology.

TotalOffset = MatrixOffset + (sizeof(entry) * ((4 * 3) * (depth - 1)))

OR

TotalOffset = MatrixOffset + (sizeof(entry) * ((4 * 3) * (width - 1)))

The constants 4 and 3 would likely be variables COLUMNS and ROWS.

Don't ask me about the 4th dimention!

ojblass 2009-04-26 02:13:09

Answer 3

A:

Basically in a 3D arrray with row major E.g Arr[3][4][5] when u want Arr[0],it looks for the front slice of the image like above Arr[1] second slice and so on. so Arr[0] means 2D array of size [4][5] ,so every Arr[x] corresponds to x*(4*5) Now about Arr[x][y] can be thought of a 1D array of size [5] whose position is [x][y] from top view in the image above so when when we want Arr[x][y] = x*(4*5)+y*(5) now Arr[x][y][z] is the specific element of Arr[x][y] at depth z Arr[x][y][z]=x*(4*5)+y*5+z now on the basis of size of the data type u want to store in the array,the offset can be multiplied to the size get the address with respect to start

2009-04-27 16:02:50

Answer 4

A:

mrwes 2009-04-30 07:33:54

Answer 5

+1 A:

Don't artificially constrain yourself by focusing on 3-dimensional and 2-dimensional. Instead focus on learning the expression for addressing n-dimensional arrays.

Expressing n-dimensional addressing would solidfy your grasp on this subject and will be easier to remember one formula rather than separate formulas for 2d and 3d addressing.

Here's my attempt at n-dimensional addressing:

#define LEN 10

int getValue_nDimensions( int * baseAddress, int * indexes, int nDimensions ) {
    int i;
    int offset = 0;
    for( i = 0; i < nDimensions; i++ ) {
        offset += pow(LEN,i) * indexes[nDimensions - (i + 1)];
    }

    return *(baseAddress + offset);
}

int main() {
    int i;
    int * baseAddress;
    int val1;
    int val2;

    // 1 dimensions
    int array1d[LEN];
    int array1d_indexes[] = {2};
    int array1d_nDimensions = 1;
    baseAddress = &array1d[0];
    for(i = 0; i < LEN; i++) { baseAddress[i] = i; }
    val1 = array1d[2];
    val2 = getValue_nDimensions( // Equivalent to: val1 = array1d[2];
        baseAddress,
        &array1d_indexes[0],
        array1d_nDimensions
    );
    printf("SANITY CHECK: %d %d\n",val1,val2);

    // 3 dimensions
    int array3d[LEN][LEN][LEN];
    int array3d_indexes[] = {2,3,4};
    int array3d_nDimensions = 3;
    baseAddress = &array3d[0][0][0];
    for(i = 0; i < LEN*LEN*LEN; i++) { baseAddress[i] = i; }
    val1 = array3d[2][3][4];
    val2 = getValue_nDimensions( // Equivalent to: val1 = array3d[2][3][4];
        baseAddress,
        &array3d_indexes[0],
        array3d_nDimensions
    );
    printf("SANITY CHECK: %d %d\n",val1,val2);

    // 5 dimensions
    int array5d[LEN][LEN][LEN][LEN][LEN];
    int array5d_indexes[] = {2,3,4,5,6};
    int array5d_nDimensions = 5;
    baseAddress = &array5d[0][0][0][0][0];
    for(i = 0; i < LEN*LEN*LEN*LEN*LEN; i++) { baseAddress[i] = i; }
    val1 = array5d[2][3][4][5][6];
    val2 = getValue_nDimensions( // Equivalent to: val1 = array5d[2][3][4][5][6];
        baseAddress,
        &array5d_indexes[0],
        array5d_nDimensions
    );
    printf("SANITY CHECK: %d %d\n",val1,val2);

    return 0;
}

Output:

SANITY CHECK:     2     2
SANITY CHECK:   234   234
SANITY CHECK: 23456 23456

Trevor Boyd Smith 2009-04-30 13:06:33

ansaurus

tags:

views:

answers:

array offset calculations in multi dimensional array (column vs row major)

related questions