Confusion about row-major and column-major

Discussion in 'C++' started by Jef Driesen, Jan 12, 2006.

  1. Jef Driesen

    Jef Driesen Guest

    I'm working on a project where i need to exchange multidimensional data
    between C/C++ (row-major) and matlab (column-major). I understand the
    difference between those two mappings to linear memory.

    Suppose I need an S1 x S2 x ... x Sn dimensional array A. I can have the
    same layout in memory by reversing the dimensions:

    A[S1]...[Sn] == A(Sn,...,S1)

    where I used the C/C++ notation for row-major and the matlab notation
    for column-major (and forget about the issue of zero-based vs one-based
    access). So far no problem.

    But when I start "naming" the dimensions (with row and column), this
    reversing does not seem to hold anymore. Let my explain that by
    progressively adding dimensions in both cases: (r=row,c=column,p=plane)

    C/C++ (row-major):

    1D: [c] --> row vector
    2D: [r][c]
    3D: [p][r][c]

    Matlab (column-major):

    1D: (r) --> column vector
    2D: (r,c)
    3D: (r,c,p)

    As you can see in 3D, the order of the dimensions is not what I
    expected. r and c are not in reverse order. And the more I start
    reasoning about it, the more I get confused. What am I missing?
    Jef Driesen, Jan 12, 2006
    #1
    1. Advertising

  2. Jef Driesen

    Heinz Ozwirk Guest

    "Jef Driesen" <> schrieb im Newsbeitrag
    news:dq5b9m$eh0$...
    > C/C++ (row-major):
    >
    > 1D: [c] --> row vector
    > 2D: [r][c]
    > 3D: [p][r][c]
    >
    > Matlab (column-major):
    >
    > 1D: (r) --> column vector
    > 2D: (r,c)
    > 3D: (r,c,p)
    >
    > As you can see in 3D, the order of the dimensions is not what I expected.
    > r and c are not in reverse order. And the more I start reasoning about it,
    > the more I get confused. What am I missing?


    You start with two different things - a row vector in C++ and a column
    vector in Matlab. I don't know what Matlab does, but in C++ you get

    int A1[n1];
    one array with n1 elements

    int A2[n2][n1];
    n2 arrays, where each element is an array with n1 elements

    int A3[n3][n2][n1];
    n3 arrays, where each element is an array with n2 elements, where each
    element is an array with n1 elements.

    You can call A1 a row vector or a column vector. C++ doesn't care, but it
    influences the use of 2D or 3D arrays. If you call A1 a row vector, the last
    subscript refers to a column, the second to last to a row, and the third to
    last to a plane. (I don't have names for other dimensions, so I better stop
    here.) Now if you call A1 a column vector, the last subscript selects its
    row, the second to last its column, and the third to last again selects a
    plane. Using your notation, in the second case you get

    1D: [r]
    2D: [c][r]
    3D: [p][c][r]

    What you have to be carefull with, is the mapping to linear memory. For a 1D
    array it is easy. In memory you have A1[0], A1[1], ... A1[n1-1]. For a 2D
    array you get A2[0][0], A2[0][1], ... A2[0][n1-1], A2[1][...], ...
    A2[n2-1][n1-1].

    For a 3D array you'll find A3[i3][i2][i1] at offset (i3 * n2 + i2) * n1 + i1
    in linear memory (ignoring the size of individual elements).

    HTH
    Heinz
    Heinz Ozwirk, Jan 12, 2006
    #2
    1. Advertising

  3. Jef Driesen

    Jef Driesen Guest

    Heinz Ozwirk wrote:
    > "Jef Driesen" <> schrieb im Newsbeitrag
    > news:dq5b9m$eh0$...
    >> C/C++ (row-major):
    >>
    >> 1D: [c] --> row vector
    >> 2D: [r][c]
    >> 3D: [p][r][c]
    >>
    >> Matlab (column-major):
    >>
    >> 1D: (r) --> column vector
    >> 2D: (r,c)
    >> 3D: (r,c,p)
    >>
    >> As you can see in 3D, the order of the dimensions is not what I expected.
    >> r and c are not in reverse order. And the more I start reasoning about it,
    >> the more I get confused. What am I missing?

    >
    > You start with two different things - a row vector in C++ and a column
    > vector in Matlab. I don't know what Matlab does, but in C++ you get


    I started with a row vector in C++ and a column vector in Matlab,
    because that seemed to me the most "natural" way, associated with each
    memory layout.

    The matlab notation for a 3D array is A(row,column,plane).

    > int A1[n1];
    > one array with n1 elements
    >
    > int A2[n2][n1];
    > n2 arrays, where each element is an array with n1 elements
    >
    > int A3[n3][n2][n1];
    > n3 arrays, where each element is an array with n2 elements, where each
    > element is an array with n1 elements.


    As long as you don't start naming the dimensions, everything is fine.
    This is basically the structure (I hope my ascii drawing does not get
    destroyed):

    A3
    ---
    | | -> A2
    --- ---
    | | | | -> A1
    --- --- ---
    | | | | | |
    --- --- ---
    | | | |
    --- ---
    | |
    ---

    > You can call A1 a row vector or a column vector. C++ doesn't care, but it
    > influences the use of 2D or 3D arrays. If you call A1 a row vector, the last
    > subscript refers to a column, the second to last to a row, and the third to
    > last to a plane. (I don't have names for other dimensions, so I better stop
    > here.) Now if you call A1 a column vector, the last subscript selects its
    > row, the second to last its column, and the third to last again selects a
    > plane. Using your notation, in the second case you get
    >
    > 1D: [r]
    > 2D: [c][r]
    > 3D: [p][c][r]


    For the 3D case this is perfectly consistent with idea of reversing the
    dimensions. But now the last dimensions (index [r], which is actually a
    column) is stored continuously in memory. And this contradicts with the
    term row-major.

    > What you have to be carefull with, is the mapping to linear memory. For a 1D
    > array it is easy. In memory you have A1[0], A1[1], ... A1[n1-1]. For a 2D
    > array you get A2[0][0], A2[0][1], ... A2[0][n1-1], A2[1][...], ...
    > A2[n2-1][n1-1].
    >
    > For a 3D array you'll find A3[i3][i2][i1] at offset (i3 * n2 + i2) * n1 + i1
    > in linear memory (ignoring the size of individual elements).


    Mapping an element to linear memory is not too difficult because it does
    not depend on my naming issue.
    Jef Driesen, Jan 12, 2006
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. kokwooi

    Major Major Problem With ASP.NET

    kokwooi, Sep 18, 2003, in forum: ASP .Net
    Replies:
    6
    Views:
    664
    NuTcAsE
    Sep 19, 2003
  2. Bazza Formez
    Replies:
    4
    Views:
    400
    Vanni Tomezzoli
    Dec 9, 2004
  3. johnsonlim026
    Replies:
    0
    Views:
    932
    johnsonlim026
    Feb 27, 2010
  4. D
    Replies:
    0
    Views:
    205
  5. ara howard
    Replies:
    0
    Views:
    224
    ara howard
    Oct 28, 2003
Loading...

Share This Page