Sparse Arrays
The TriangularArray class saves roughly half of an array's space by avoiding storing duplicate values. In some applications, an array may contain very few values other than some default.
For example, suppose your application deals with connectivity in an airline network connecting 100 cities. The array entry
is_connected(R, C) is true if there is a flight between city
R and city
C. You probably don't have flights connecting all the 10,000 possible pairs of cities. In fact, you might only fly 200 flights between the cities; customers use connecting flights to go from city to city when no nonstop flight is available.
In this example, the array contains only 200 of 10,000 possible entries. Storing this data in a triangular array would save space but it would still contain 5,000 entries, 96 percent of which would be false.
You can make this array more efficient by using a sparse array. The idea is to store only the entries that have a non-default value. Whenever you need to look up an entry, you assume that any missing item has the default value.
Classically, you would build a sparse array with a linked data structure. A Row class contains a row number, a link to the next row, and a link to the first item in the row. The Item class contains a column number, the data for that entry, and a link to the next entry in the row.
To find an item, you search through the linked list of row objects until you find the row number you want. Then you search through that row's linked list of items until you find the column number you want and then you return that item's data. If you can't find the row, or can't find the item in the row, you return the default value.
To set an item's value, you first try to find it in same way. If the item isn't present, you add it (possibly creating a new row if the item's row wasn't there). Then you set the item's value.
Finally, to set an item to the default value, you find it and remove it from the data structure.
All of this is an interesting character-building exercise and I encourage you to give it a try in your spare time, but the .NET Framework's Dictionary class gives you a much simpler (easier to understand and debug) alternative. The following code shows a SparseArray class that uses a Dictionary object:
Public Class SparseArray(Of T As IComparable)
Private m_Dict As Dictionary(Of String, T)
Private m_Default As T
Public Sub New(ByVal default_value As T)
m_Dict = New Dictionary(Of String, T)
m_Default = default_value
End Sub
' Get or set this item.
Default Public Property Item( _
ByVal r As Integer, ByVal c As Integer) As T
Get
Dim key As String = r & "," & c
If m_Dict.ContainsKey(key) Then Return m_Dict(key)
Return m_Default
End Get
Set(ByVal value As T)
Dim key As String = r & "," & c
If value.Equals(m_Default) Then
m_Dict.Remove(key)
Else
m_Dict(key) = value
End If
End Set
End Property
End Class
This is a generic class based on a type
T that implements the IComparable interface. The class starts by defining a generic Dictionary object that uses strings for keys and stores objects of type
T. The class's constructor creates the Dictionary and saves the sparse array's default value.
The
Item property uses the Dictionary to get and set values. The
Get procedure composes a string key for the item and determines whether the item is in the Dictionary. If the item is present, the procedure returns its value. If the item is not in the Dictionary, the procedure returns the default value.
The
Set procedure also composes a key for the item. Then, if the item's new value equals the default value (
T must implement IComparable, so the test will always work), the procedure removes the item from the dictionary. If the new value is not the default value, the procedure sets the new value in the Dictionary.
The SparseArray program in the
downloadable code demonstrates the SparseArray class.
Previous Page
