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 N_k (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 world stands out on either side
No wider than the heart is wide;
Above the world is stretched the sky,—
No higher than the soul is high.”
—Edna St. Vincent Millay (1892–1950)

“The truth is that a Pigmy and a Patagonian, a Mouse and a Mammoth, derive their dimensions from the same nutritive juices.... [A]ll the manna of heaven would never raise the Mouse to the bulk of the Mammoth.”
—Thomas Jefferson (1743–1826)