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:

    “We were as twinned lambs that did frisk i’ the sun
    And bleat the one at th’ other. What we changed
    Was innocence for innocence; we knew not
    The doctrine of ill-doing, nor dreamed
    That any did. Had we pursued that life,
    And our weak spirits ne’er been higher reared
    With stronger blood, we should have answered heaven
    Boldly “Not guilty,” the imposition cleared
    Hereditary ours.”
    —William Shakespeare (1564–1616)

    “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)