RSS Feed
Download our iPhone app
Browse DevX
Sign up for e-mail newsletters from DevX


Use Specialty Arrays to Accelerate Your Code : Page 4

Learn how to build unusually shaped triangular and sparse arrays, and arrays with non-zero lower bounds that are much faster than those provided by the standard .NET Array class.

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.

Rod Stephens is a consultant and author who has written more than a dozen books and two hundred magazine articles, mostly about Visual Basic. During his career he has worked on an eclectic assortment of applications for repair dispatch, fuel tax tracking, professional football training, wastewater treatment, geographic mapping, and ticket sales. His VB Helper web site receives more than 7 million hits per month and provides three newsletters and thousands of tips, tricks, and examples for Visual Basic programmers.
Email AuthorEmail Author
Close Icon
Thanks for your registration, follow us on our social networks to keep up-to-date