Row-major Order - Generalization To Higher Dimensions

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 array with dimensions Nk (k=1...d). A given element of this array is specified by a tuple of d (zero-based) indices .

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.

Read more about this topic:  Row-major Order

Famous quotes containing the words higher and/or dimensions:

    “The lesson learned here is a costly one: If you stand up for your principles, follow the law, and win massively, you lose totally.”
    —Linda J. Carpenter, U.S. educator. As quoted in the Chronicle of Higher Education, p. A38 (July 15, 1992)

    “It seems to me that we do not know nearly enough about ourselves; that we do not often enough wonder if our lives, or some events and times in our lives, may not be analogues or metaphors or echoes of evolvements and happenings going on in other people?—or animals?—even forests or oceans or rocks?—in this world of ours or, even, in worlds or dimensions elsewhere.”
    —Doris Lessing (b. 1919)