Make a class that wraps arrays with non-zero lower bounds in C#

[arrays with non-zero lower bounds]

The example Make arrays with non-zero lower bounds in C# shows how to use the Array class to make an array with non-zero lower bounds. Unfortunately the syntax is unnatural, requiring you to use method calls instead of normal array indexing syntax. It’s also fairly slow.

This example shows how to make a class that lets you create multidimensional arrays with non-zero lower bounds that you use array-style indexing.


The BoundsArray class stores multidimensional values in a one-dimensional array as shown in the following picture.



This arrangement is called “row-major order” because the rows are laid out first.

Now for an item at position (r, c) in the first array, what’s the index of that item in the second array? If the indexes start at 0, then the position is r * 5 + c. In this example 5 is the number of items in a column. The r * 5 term skips r rows. Remember that indexing starts at 0 so if r is 0, we skip no rows. Adding c moves the position c columns to the right. Because indexing starts at 0, that puts us in the correct spot in the one-dimensional array.

Now consider a three-dimensional case. You can map items in a three-dimensional array into a one-dimensional array in a similar manner by dividing the block of data into two-dimensional “slices.” Write each “slice” into the one-dimensional array as before in row-major order.

You can map indexes x, y, z, … in the multidimensional array to the one-dimensional array in a way that’s similar to the previous method.

To skip x “slices,” multiply x by the size of a “slice.” In a two-dimensional case, a “slice” is a row so you would multiply x by the number of items in a row, which is the number of columns.

Next skip y “sub-slices” where a “sub-slice” is the next smaller group of items. In a two-dimensional case, this would be a single cell.

Continue in this way until you get to the final index, which you multiply by 1.

(Sorry if this is a bit confusing. It’s hard to visualize. It may help if you draw a small three-dimensional example.)

The BoundsArray class isn’t too long but it’s confusing so the rest of this post describes it in pieces. The following code shows the class’s declaration and fields.

class BoundsArray<T>
{
    // A one-dimensional array holding the data.
    T[] Data;

    // The bounds.
    int NumDimensions;
    int[] LowerBound, Offset;
    ...
}

This is a generic class so it can make arrays of any data type. The class stores the array’s items in a one-dimensional array of type T named Data.

The class stores the number of the array’s dimensions in the NumDimensions variable. It uses the LowerBound array to hold the lower bounds for the dimensions. The Offset array holds the sizes of the array’s “slices” so it can calculate offsets in the one-dimensional array.

The following code shows the class’s constructor.

// Constructor.
public BoundsArray(params int[] bounds)
{
    // Make sure there is an even number of bounds.
    if (bounds.Length % 2 == 1)
        throw new ArgumentException(
            "Number of bounds must be even.", "bounds");

    // Make sure there are at least two bounds.
    if (bounds.Length < 2)
        throw new ArgumentException(
            "There must be at least two bounds, " +
                one upper and one lower.", "bounds");

    // Get the bounds.
    NumDimensions = (int)(bounds.Length / 2);
    LowerBound = new int[NumDimensions];
    Offset = new int[NumDimensions];
    int total_size = 1;
    for (int i = NumDimensions - 1; i >= 0; i--)
    {
        Offset[i] = total_size;

        LowerBound[i] = bounds[2 * i];
        int upper_bound = bounds[2 * i + 1];
        int bound_size = upper_bound - LowerBound[i] + 1;
        total_size *= bound_size;
    }

    // Allocate room for all of the items.
    Data = new T[total_size];
}

The class’s constructor expects a series of upper and lower bounds. For example, the statement BoundsArray(2001, 2010) creates a one-dimensional array with lower bound 2001 and upper bound 2010.

The constructor saves the number of dimensions and loops through the bounds. It saves the lower bounds in the LowerBound array. It calculates the size of each dimension and multiplies that size by total_size. When the loop finishes, total_size contains the total size of the array.

Additionally, while it is in this loop, total_size gives the size of the next dimensional “slice” of the array. Initially total_size is 1 and represents the size of a single cell. During the next pass through the loop, total_size holds the size of a “row” of cells. During the next loop it holds the size of a two-dimensional “slice” and so forth. The program saves these sizes in the Offsets array so it can later use them to calculate array indexes in the one-dimensional Data array.

After this loop finishes, the program allocates the Data array, making it big enough to hold all of the items.

The following code shows the class’s indexer property. This is what lets you use index-style syntax to address array entries.

// The indexer.
public T this[params int[] indexes]
{
    get
    {
        if (indexes.Length != NumDimensions)
            throw new IndexOutOfRangeException(
                "Number of indexes does not match " +
                    "number of dimensions");
        return Data[Index(indexes)];
    }
    set
    {
        if (indexes.Length != NumDimensions)
            throw new IndexOutOfRangeException(
                "Number of indexes does not match " +
                    "number of dimensions");
        Data[Index(indexes)] = value;
    }
}

The indexer calls the Index method (described shortly) to map the indexes (x, y, z, etc.) in the multidimensional array to an index in the one-dimensional Data array, and then gets or sets the appropriate value. For more information on indexers, see Make a default indexer property for a class in C#.

The following code shows the Index method that maps indexes in the multidimensional array to an index in the one-dimensional Data array.

// Calculate the index for a series of indexes.
private int Index(params int[] indexes)
{
    int total_offset = 0;
    for (int i = 0; i < indexes.Length; i++)
    {
        total_offset += (indexes[i] - LowerBound[i]) * Offset[i];
    }
    return total_offset;
}

This code loops through the indexes, multiplying each by its Offsets value and adding the results. Go back to the discussion of how items are mapped into the one-dimensional array at the beginning of this post for details.

The example program does two things. First, when it loads, it creates a three-dimensional BoundsArray and fills in all of its values. It then retrieves the values and displays them in a TextBox so you can see that it successfully saved and retrieved the values.

Second, the program compares the speeds of the Array class, the BoundsArray class, and a simple three-dimensional array variable. Enter the number of trials you want to perform and click Go. For each kind of array, the program creates the array, fills it, and then retrieves its values.

If you look closely at the first picture, you’ll see that the Array class took 3.02 seconds and the BoundsArray class took 2.05 seconds. The plain array took only 0.31 seconds.

The following code fragment shows how the program allocates the three kinds of arrays.

// Array size constants.
const int xmin = 1001, num_x = 50, xmax = xmin + num_x - 1;
const int ymin = 2001, num_y = 50, ymax = ymin + num_y - 1;
const int zmin = 2001, num_z = 50, zmax = zmin + num_z - 1;

// Use the Array class.
Array array_class = Array.CreateInstance(
    typeof(int),
    new int[] { num_x, num_y, num_z },
    new int[] { xmin, ymin, zmin });
...
array_class.SetValue(value, x, y, z);
...

// Use the BoundsArray class.
BoundsArray<int> bounds_array = 
    new BoundsArray<int>(xmin, xmax, ymin, ymax, zmin, zmax);
...
bounds_array[x, y, z] = value;
...

// Plain array.
int[, ,] plain_array = new int[num_x, num_y, num_z];
...
plain_array[x, y, z] = value;
...

The BoundsArray class has a more natural constructor and array-style indexing than the Array class does, and it’s faster. A plain old array is even better, but it requires that all of the lower bounds be 0. I have to think that if Microsoft allowed plain array variables to have non-zero lower bounds, it would be almost as fast as the existing plain array.


Download Example   Follow me on Twitter   RSS feed   Donate




This entry was posted in arrays, performance, variables and tagged , , , , , , , , , , , , . Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *