A Big Sparse Matrix

In my last blog post I described an implementation in C# of a big (larger than 2 GB) array of int values. This weekend I was working with a very large graph and I needed a way to represent this graph in memory. Each node/vertex of the graph is a 0-based integer. A regular matrix of type int would require too much memory, and most of the entries would be 0. A regular sparse graph implemented as jagged matrix, that is, an array of int arrays works for big graphs, but didn’t work for the huge graph I was working with. So I created a custom data structure. Naming this data structure was troublesome – it represents a graph, as a sparse matrix, realized as a modified array of arrays of type int. Anyway I called this thing a BigArrayOfArraysOfInt. Some example calls are:

(1) BigArrayOfArraysOfInt a =
new BigArrayOfArraysOfInt(11);
(2) a.CreateRow(7, 5);
(3) a.CreateRow(1, 6);
(4) a.SetValue(7, 2, 9);
(5) int[] data = new int[]{2,4,6,8};
(6) a.SetRow(0, data);
(7) a.Display();
(8) int x = a.GetValue(7, 2);

Line 1 instantiates the sparse matrix to 11 rows. The matrix is broken up into blocks of 3 arrays (where the last block may be smaller), where the 3 is hard-coded. So behind the scenes there would be 3 blocks of 3 arrays and a fourth block of 2 arrays. Line 2 creates a row of 5 ints at row [7] of the structure. The 5 values are automatically initialized to 0. Line 3 creates an array of length 6 at row [1]. Line 4 sets row 7, col 2 to 9. Line 5 creates an array of 4 ints and line 6 attaches that array to row [0] of the matrix. Line 7 displays a representation of the matrix to console. Line 8 fetches the value at row 7, col 2 (which is 9 from line4). I’ll detail the implementation in my next post.

Advertisements
This entry was posted in Machine Learning, Software Test Automation. Bookmark the permalink.