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:

    “I remain just one thing, and one thing only—and that is a clown. It places me on a far higher plane than any politician.”
    —Charlie Chaplin (1889–1977)

    “Why is it that many contemporary male thinkers, especially men of color, repudiate the imperialist legacy of Columbus but affirm dimensions of that legacy by their refusal to repudiate patriarchy?”
    —bell hooks (b. c. 1955)