Login | Register   
LinkedIn
Google+
Twitter
RSS Feed
Download our iPhone app
TODAY'S HEADLINES  |   ARTICLE ARCHIVE  |   FORUMS  |   TIP BANK
Browse DevX
Sign up for e-mail newsletters from DevX


advertisement
 

Use Specialty Arrays to Accelerate Your Code

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.


advertisement
was surfing the web the other day, looking for Visual Basic questions to answer, when I stumbled across an old FAQ that explained why Visual Basic no longer has arrays with non-zero lower bounds. I don't really buy the explanation given by Paul Vick at (it seems like the needs of the none outweighing the needs of the many to me) but it did start me thinking about arrays.

Visual Studio provides arrays of any data type. You can make one-, two-, and higher-dimensional arrays of integers, strings, objects, structures, or whatever. But there are a couple of useful kinds of arrays that Visual Studio doesn't provide. This article explains how you can implement three of these: triangular arrays, sparse arrays, and arrays with non-zero lower bounds.

When you create a typical array, Visual Studio allocates memory for a block of items that includes one entry for every possible combination of indexes. For example, the following code allocates an array of Booleans containing 1 million entries:

Dim is_connected(1000, 1000) As Boolean

In some applications, you don't really need all these entries. For example, suppose the application tests connectivity in an electric, airline, or other network and the method is_connected(R, C) returns true if there is a link connecting location R with location C. Assuming the network is non-directional (so that a link between R and C also means there is a link between C and R), then this array contains a lot of duplicated information. If is_connected(R, C) is true then is_connected(C, R) is also true.

You can avoid storing all of this duplicated information and save half of the array's space by using a triangular array. A triangular array stores only the values for is_connected(R, C) where R >= C. It deduces the values of other entries by switching the order of R and C.

The TriangularArray class described here saves this space by mapping the entries in the array into a one-dimensional storage array. Figure 1 shows a small triangular array on top and the linear storage of the array's values on the bottom.

 
Figure 1. Triangle Tricks: The TriangularArray class stores entries for a triangular array (top) in a linear storage array (bottom).
The only tricky part is figuring out the index in the storage array that corresponds to an entry in the triangular array.

Consider an item in array position (R, C), where "R" is the row and "C" is the column. The rows above this one contain 1 + 2 + 3 + ... + R entries. You may recall that there is a simple formula for this kind of sum: 1 + 2 + ... + R = R * (R + 1) / 2.

Now notice that the number of items to the left of this one in its row is C, so the total number of items that come before this one is R * (R + 1) / 2 + C.

For example, consider item E in Figure 1. This item is at position (2, 1) in the triangular array (be sure to start counting from index 0), so its position in the storage array is 2 * (2 + 1) / 2 + 1 = 3 + 1 = 4, which you can verify in Figure 1.

The following code shows a TriangularArray class. I've removed some bounds checking code to make the code easier to read:

Public Class TriangularArray(Of T) Private m_Width As Integer Private m_Values() As T ' Allocate storage. Public Sub New(ByVal width As Integer) m_Width = width ReDim m_Values(m_Width * (m_Width + 1) \ 2 - 1) End Sub ' Return the item at position (row, column). Default Public Property Item( _ ByVal r As Integer, ByVal c As Integer) Get Return m_Values(ItemIndex(r, c)) End Get Set(ByVal value) m_Values(ItemIndex(r, c)) = value End Set End Property ' Calculate the item's position in the array. Private Function ItemIndex(ByVal r As Integer, _ ByVal c As Integer) As Integer If r >= c Then Return r * (r + 1) \ 2 + c Return c * (c + 1) \ 2 + r End Function End Class

The class's constructor takes the array's width as a parameter, and allocates enough space to hold all of the array's items.

The Item property gets or sets an item in the array. It calls the ItemIndex method to convert the item's row and column numbers into an index in the storage array and gets or sets the appropriate value.

The Default keyword makes Item the default property for the class. That means the main program can treat an object of the class as if it were an array and the "index" passed to the object is sent as a parameter to the property. (In C#, this property is the class indexer.)

The ItemIndex method simply returns R * (R + 1) / 2 + C as described earlier. If R < C, it swaps the roles of R and C.

The sample program TriangularArray (available with the downloadable code for this article in both Visual Basic and C#), demonstrates the class for the array shown in Figure 1. (For extra credit, try to figure out how to modify the class slightly to handle arrays that don't need to contain items on the diagonal where R = C.)



Comment and Contribute

 

 

 

 

 


(Maximum characters: 1200). You have 1200 characters left.

 

 

Sitemap