Moving to Higher Dimensions
Before you see the code for this class, you should understand how to lay out a multi-dimensional array in memory. (In fact, this is the same way compilers do it.) For now, assume all of the dimensions' lower bounds are zero and we'll remove that restriction later.
This example lays out its values in
row-major order. That means all the elements in the early dimensions are grouped together in memory. This makes the most sense if you think of a two-dimensional array laid out in a one-dimensional stretch of memory as shown in
Figure 2. The top of the figure shows the array in its two-dimensional logical form. The bottom shows the array's items placed in a one-dimensional memory.
 | |
| Figure 2. Two for One: The two-dimensional array at the top of the figure is laid out in at the bottom in one-dimensional memory, in row-major order. |
In
Figure 2, you can see that the items in each of the array's rows are adjacent to each other in memory.
To calculate the location of an item in the one-dimensional memory, you multiply the item's row number (starting at zero) by the number of items in a row, and then add the item's column number (again starting with zero). The array in
Figure 2 has four items in each row so, for example, the item G (at row 1 column 2) has memory location
1 * 4 + 2 = 6. You can verify this by counting the entries at the bottom (be sure to start counting from zero.)
Now consider the three-dimensional case shown in
Figure 3. The top shows a three-dimensional 3 x 2 x 2 array where the dimensions sequentially run left-to-right, top-to-bottom, and front-to-back. For example, item
F is at position (
2, 1, 0).
 | |
| Figure 3. Higher Dimensions: Items in higher-dimensional arrays are packed first in one-dimensional groups and then in higher-dimensional groups. |
In the one-dimensional representation at the bottom of
Figure 3, items are first placed in one-dimensional groups. Those are combined to form two-dimensional groups, which are combined in turn for form three-dimensional groups. For higher-dimensional arrays, the process would continue.
Now you can generalize the method used earlier for finding an item in a two-dimensional array to this higher-dimensional version. The idea is to determine the number of each type of grouping that comes before an item in memory.
For example, consider item
L in the lower representation in
Figure 3. To the immediate left of item
L, there are two single items
J and
K. To the left of those items is a one-dimensional grouping containing items
G through
I. To the left of that group is a two-dimensional grouping containing items
A through
F. To find the location of item
L, you add up the sizes of these groupings to the left:
2 * 1 + 1 * 3 + 1 * 6 = 11. You can verify that this is the location of item
L in the lower part of
Figure 3.
More generally, suppose you are working with an N-dimensional array where the dimensions have lengths
L1,
L2, and so forth. (In
Figure 3, the array's dimensions are
L1 = 3,
L2 = 2, and
L3 = 2.) Knowing the dimension lengths, you can calculate the sizes of the various groupings. These sizes are
L1 for a one-dimensional grouping,
L1 * L2 for a two-dimensional grouping,
L1 * L2 * L3 for a three-dimensional grouping, and so forth. (In
Figure 3, the sizes are
3,
3 * 2 = 6, and
3 * 2 * 2 = 12.)
Now suppose an item has indexes
I1,
I2,
I3, and so forth. Then the layout has
I1 of the smallest groupings before it in the memory representation,
I2 of the second smallest groupings before it, and so forth.
In the previous example, item
L has indexes (
2, 1, 1) so it comes after two of the smallest groupings (one item each), one of the next largest grouping (three items), and one of the largest grouping (six items) for a total of
2 * 1 + 1 * 3 + 1 * 6 = 11 items before item
L.
This all seems rather complex but the MultiDArray class shown in
Listing 1 is actually relatively short and simple if you can keep the general ideas straight in your mind. (Again, I have removed bounds checking code to keep the code simple.) The class uses private variables to record the array's lower bounds and the length of each dimension. The
m_SkipFactors array contains the sizes of the various groupings in order from largest to smallest so the program can easily calculate an item's index. The
m_Values array holds the data.
The class's constructor saves the lower bounds and dimension lengths. It then calculates the skip factors. The first skip factor is
1. Others are the sizes of the groupings—in increasing order so they match up with the indexes of an item. For the previous example, the skip factors are
1,
3, and
6. The constructor finishes by creating a one-dimensional array to hold all the values.
The
Item property takes as parameters the indexes of the item that should be
get or
set. Visual Basic doesn't allow you to use the
Default keyword on a property with all optional parameters so
index0 is declared separately. (This isn't a restriction in C# so the code is a little more elegant.) The
Item property calls the
ItemIndex method to calculate the index of the item in the storage array and uses that index to get or set the value.
The
ItemIndex method first calculates the position of an item in the storage array. It copies the indexes into a single array to make working with them easier and then loops through the indexes. For each index, it subtracts that dimension's lower bound (here's where we get back to non-zero lower bounds), multiplies by the dimension's skip factor, and adds the result to the total offset into the storage array.
The following code how a program can use the MultiDArray class to build an array similar to the one shown in
Figure 3:
 | |
| Figure 4. Time Trials: With zero lower bounds, nothing beats a normal array. But for non-zero lower bounds, the OneDArray, TwoDArray, and MultiDArray classes leave the Array class in the dust. |
Dim lower_bounds() As Integer = {0, 0, 0}
Dim lengths() As Integer = {3, 2, 2}
Dim arr As New MultiDArray( _
Of String)(lower_bounds, lengths)
arr(0, 0, 0) = "A"
arr(1, 0, 0) = "B"
arr(2, 0, 0) = "C"
arr(0, 1, 0) = "D"
arr(1, 1, 0) = "E"
arr(2, 1, 0) = "F"
arr(0, 0, 1) = "G"
arr(1, 0, 1) = "H"
arr(2, 0, 1) = "I"
arr(0, 1, 1) = "J"
arr(1, 1, 1) = "K"
arr(2, 1, 1) = "L"
In the
sample code the
MultiDArray program example demonstrates the OneDArray, TwoDArray, and MultiDArray classes.
Figure 4 shows the program in action. As you can see, a normal array is much faster than any other solution if you can use zero lower bounds. But if you need non-zero lower bounds, the Array class compares pretty badly to the OneDArray, TwoDArray, and MultiDArray classes. The more specialized OneDArray and TwoDArray classes are considerably faster than MultiDArray but they don't have as much flexibility. If your project requirements change so you suddenly need a seventeen-dimensional array, you can immediately plug in a MultiDArray class, and later, if there's a need, you can build a customized array class just to handle this odd case.
Previous Page
