Row-major order

Row-major order

In computing, row-major order and column-major order describe methods for storing multidimensional arrays in linear memory. Following standard matrix notation, rows are numbered by the first index of a two-dimensional array and columns by the second index. Array layout is critical for correctly passing arrays between programs written in different languages. It is also important for performance when traversing an array because accessing array elements that are contiguous in memory is usually faster than accessing elements which are not, due to caching.

Row-major order is used in C,PL/I; column-major order is used in Fortran and MATLAB.

Contents

Row-major order

In row-major storage, a multidimensional array in linear memory is accessed such that rows are stored one after the other. It is the approach used by the C programming language as well as many other languages, with the notable exceptions of Fortran and MATLAB.

When using row-major order, the difference between addresses of array cells in increasing rows is larger than addresses of cells in increasing columns. For example, consider this 2×3 array:

 \begin{bmatrix}
1 & 2 & 3 \\
4 & 5 & 6 \end{bmatrix}

An array declared in C as

int A[2][3] = { {1, 2, 3}, {4, 5, 6} };

would be laid out contiguously in linear memory as:

 1  2  3  4  5  6

To traverse this array in the order in which it is laid out in memory, one would use the following nested loop:

for (i = 0; i < 2; i++) 
    for (j = 0; j < 3; j++) 
        printf("%d\n", A[i][j]);

The difference in offset from one column to the next is 1 and from one row to the next is 3. The linear offset from the beginning of the array to any given element A[row][column] can then be computed as:

offset = row*NUMCOLS + column

where NUMCOLS is the number of columns in the array.

The above formula only works when using the C convention of labeling the first element 0. In other words, row 1, column 2 in matrix A, would be represented as A[0][1].

Note that this technique generalizes, so a 2×3×4 array looks like:

int A[2][3][4] = {{{1,2,3,4}, {5,6,7,8}, {9,10,11,12}}, {{13,14,15,16}, {17,18,19,20}, {21,22,23,24}}};

and the array would be laid out in linear memory as:

 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24

Column-major order

Column-major order is a similar method of flattening arrays onto linear memory, but the columns are listed in sequence. The programming languages Fortran, MATLAB,[1] Octave, R[2] and the shading languages GLSL and HLSL use column-major ordering. The array

 \begin{bmatrix}
1 & 2 & 3 \\
4 & 5 & 6 \end{bmatrix}

if stored contiguously in linear memory with column-major order would look like the following:

 1  4  2  5  3  6

The memory offset could then be computed as:

offset = row + column*NUMROWS

where NUMROWS represents the number of rows in the array—in this case, 2.

Treating a row-major array as a column-major array is the same as transposing it. Because performing a transpose requires data movement, and is quite difficult to do in-place for non-square matrices, such transpositions are rarely performed explicitly. For example, software libraries for linear algebra, such as the BLAS, typically provide options to specify that certain matrices are to be interpreted in transposed order to avoid the necessity of data movement.

Generalization to higher dimensions

It is possible to generalize both of these concepts to arrays with greater than two dimensions. For higher-dimensional arrays, the ordering determines which dimensions of the array are more consecutive in memory. Any of the dimensions could be consecutive, just as a two-dimensional array could be listed column-first or row-first. The difference in offset between listings of that dimension would then be determined by a product of other dimensions. It is uncommon, however, to have any variation except ordering dimensions first to last or last to first. These two variations correspond to row-major and column-major, respectively.

More explicitly, consider a d-dimensional N_1 \times N_2 \times \cdots \times N_d array with dimensions Nk (k=1...d). A given element of this array is specified by a tuple (n_1, n_2, \ldots, n_d) of d (zero-based) indices n_k \in [0,N_k - 1].

In row-major order, the last dimension is contiguous, so that the memory-offset of this element is given by:

n_d + N_d \cdot (n_{d-1} + N_{d-1} \cdot (n_{d-2} + N_{d-2} \cdot (\cdots + N_2 n_1)\cdots)))
= \sum_{k=1}^d \left( \prod_{\ell=k+1}^d N_\ell \right) n_k

In column-major order, the first dimension is contiguous, so that the memory-offset of this element is given by:

n_1 + N_1 \cdot (n_2 + N_2 \cdot (n_3 + N_3 \cdot (\cdots + N_{d-1} n_d)\cdots)))
= \sum_{k=1}^d \left( \prod_{\ell=1}^{k-1} N_\ell \right) n_k

Note that the difference between row-major and column-major order is simply that the order of the dimensions is reversed. Equivalently, in row-major order the rightmost indices vary faster as one steps through consecutive memory locations, while in column-major order the leftmost indices vary faster.

See also

References

  1. ^ MATLAB documentation, mxCalcSingleSubscript function (retrieved from Mathworks.com, March 2010).
  2. ^ An Introduction to R, Section 5.1: Arrays (retrieved March 2010).

Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • order — orderable, adj. orderer, n. orderless, adj. /awr deuhr/, n. 1. an authoritative direction or instruction; command; mandate. 2. a command of a court or judge. 3. a command or notice issued by a military organization or a military commander to… …   Universalium

  • order — or•der [[t]ˈɔr dər[/t]] n. 1) an authoritative direction or instruction; command 2) the disposition of things following one after another; succession or sequence: alphabetical order[/ex] 3) a condition in which each thing is properly disposed… …   From formal English to slang

  • Order of Canada — Insignia of a Member of the Order of Canada Awarded by the …   Wikipedia

  • Major League (film) — Major League Theatrical release poster Directed by David S. Ward Produced by …   Wikipedia

  • order — [ôr′dər] n. [OFr ordre < L ordo (gen. ordinis), straight row, regular series, akin to ordiri, to lay the warp, hence begin, set in order, prob. < IE base * ar , to join, fit > ARM1, ART1] 1. social position; rank in the community 2. a… …   English World dictionary

  • Major depressive disorder — For other depressive disorders, see Mood disorder. Major Depressive Disorder Classification and external resources …   Wikipedia

  • Order of St. Sylvester — For the monastic order, see Sylvestrines. Order of St. Sylvester Ordo Sanctus Silvestri Papae Knight s cross of the Order of St. Sylvester (1841) Awarded by …   Wikipedia

  • order — /ˈɔdə / (say awduh) noun 1. an authoritative direction, injunction, command, or mandate. 2. Australian History → land order. 3. Also, court order. Law a direction given by a court, judge, or minister of the crown. 4. Military a command or notice… …  

  • order — Synonyms and related words: Bronze Star Medal, Croix de Guerre, Distinguished Conduct Medal, Distinguished Flying Cross, Distinguished Service Cross, Distinguished Service Medal, Distinguished Service Order, Distinguished Unit Citation, MO,… …   Moby Thesaurus

  • Major Intermediate A Hockey League — The Major Intermediate A Hockey League was an ice hockey league in Ontario, Canada, sanctioned by the Ontario Hockey Association. It existed from 1978 to 1983. Its champion was eligible to compete for the W.G. Hardy Trophy, emblematic of Canadian …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”