Big Sparse Matrix Implementation

In my last blog post I described the design of a big sparse matrix of int. Here’s some of the key implementation. The definition starts with:

class BigArrayOfArraysOfInts
{
  public readonly int[][][] master;
  public readonly int length;
  public readonly int levelZeroArrayLength;
  private int levelOneArrayLength;
  . . .

The master array can be visualized in several ways. See the image below for how I conceptualize master. The image is the result of the following code:

BigArrayOfArraysOfInt theMatrix =
  new BigArrayOfArraysOfInt(8);
theMatrix.CreateNewRow(0,4);
theMatrix.CreateNewRow(4,5);
theMatrix.SetValue(4,3,7);

The overall length field is the virtual number of rows in the matrix, 8 in this example. The level one array length is the number of blocks in the structure which is hard-coded to 3. Notice that the last block only has length 2 because that’s all that’s needed. The constructor does most of the work:

public BigArrayOfArraysOfInt(int length)
{
  this.length = length;
  this.levelOneArrayLength = 3;

  int remainder = this.length % this.levelOneArrayLength;
  if (remainder == 0)
  {
    levelZeroArrayLength = (this.length / this.levelOneArrayLength) + 0;
    this.master = new int[levelZeroArrayLength][][];
    for (int i = 0; i < levelZeroArrayLength; ++i)
    {
      master[i] = new int[this.levelOneArrayLength][];
    }
  }
  else
  {
    levelZeroArrayLength = (this.length / this.levelOneArrayLength) + 1;
    this.master = new int[levelZeroArrayLength][][];
    for (int i = 0; i < levelZeroArrayLength – 1; ++i)
    {
      master[i] = new int[this.levelOneArrayLength][];
    }
    master[levelZeroArrayLength – 1] = new int[remainder][];
  }
} // ctor()

I use the length parameter and the fixed level one length to determine how big the master array is and then allocate. The CreateNewRow method is:

public void CreateNewRow(int row, int rowLength)
{
  int levelZeroIndex = row / this.levelOneArrayLength; ;
  int levelOneIndex = row % this.levelOneArrayLength;
  this.master[levelZeroIndex][levelOneIndex] = new int[rowLength];
}

The code looks asymmetric and took me a while to figure it out. The SetValue method is:

public void SetValue(int row, int col, int value)
{
  int levelZeroIndex = row / this.levelOneArrayLength;
  int levelOneIndex = row % this.levelOneArrayLength;
  this.data[levelZeroIndex][levelOneIndex] [col] = value;
}

As I described in the previous post, I could have implemented the IEnumerable interface so I could traverse the sparse matrix in an elegant way but I prefer to work at a lower level of abstraction. For example:

public void Display()
{
  int virtualRow = 0;
  for (int i = 0; i < this.master.Length; ++i)
  {
    Console.WriteLine(“==== Block ” + i + ” ===”);
    int[][] currRow = master[i];

    for (int j = 0; j < currRow.Length; ++j)
    {
      Console.Write(“[“);
      if (virtualRow < 10) Console.Write(” “);
      Console.Write(virtualRow + “] “);
      ++virtualRow;
      Console.Write(j + ” -> “);
      int[] data = currRow[j];
      if (data == null)
      {
        Console.WriteLine(” X”);
        continue;
      }
      for (int k = 0; k < data.Length; ++k)
      {
        Console.Write(” ” + data[k]);
      }
      Console.WriteLine(“”);
    }
    Console.WriteLine(“================\n”);
  }
}

The virtualRow is a counter that indicates the row number if te sparse matrix were one big matrix. Variabe i traverse the master array. Variable j traverses each level one array. And variable k traverse the “column” arrays.


This entry was posted in Software Test Automation. Bookmark the permalink.