Matrix storage structure

[Duncan M Gunn]

Hi,

I need to store the following matrix of values:

T U V
A 2 1 1
B 2 - -
C - - 2

Where (-) is an empty cell.

The obvious solution is to store it as a 2D array, but I would like to store
this as efficiently as possible.
For example, the Matrix object need only store the cells that have a value,
if asked for a cell which is not assigned it can return a default empty
value.

I would also prefer to be able to access it by using only one index, e.g. if
only the y value is known then return a list of cells with that y value.

This could be achieved using a 1D array, where a given cell could be
accessed by multiplying the given x or y value by the respective number of
columns or rows. However, it would still require an array of x * y
elements, even when half of these elements are not required. I presume that
a completely empty x * y array of MyObject would take up x * y *
SizeOf(MyObject) space.

Does anyone know of an efficient data structure for a matrix?

Thanks,
Duncan

 

[Dan Bass]

Duncan,

An ArrayList of ArrayList's of strings would be an efficient structure.
If there are no values in certain cells, the 2nd ArrayList would simply
reference a null. This is the most minimul an empty cell can be.
It would be a good idea to wrap this in a class.

Daniel.

 

[Marcus]

Duncan,

Take a look at sparse matrix data structures. This link gives a nice
intro to them http://www.math.uu.nl/people/bisselin/PSC/psc4_2.pdf
It only make senses to use a sparse matrix if more than half your data
is empty.

Marcus

 

[Peter N Roth]

Efficiency is a tricky beast. In this case, you are making
a tradeoff between storage used and computation
time to access an element. If you have a lot of cheap
memory, you might find 2D storage a winner after all.

--
Grace + Peace,
Peter N Roth
Engineering Objects International
http://engineeringobjects.com
Home of Matrix.NET

 

[Bruce Wood]

Peter is right. The first question you have to ask is, "How big do I
expect this thing to be?"

Any sparse-matrix data structure will come with two penalties: a CPU
time hit to look up elements (_nothing_ is faster than a 2D array) and
memory overhead when storing the elements that are there.

Marcus was correct in saying that sparse data structures make sense
only if less than half your data is there, but he forgot to mention
that they also make sense only if you have lots and lots of data. If
you have only, say, a 20x20 half-full array, even of 64-bit values,
then the 12K you're going to save by not storing the empty values can
easily be eaten up (and more) by the overhead needed to maintain a more
complex data structure.

As the size of your matrix mounts, sparse array data structures look
more and more appealing. For example, those same 64-bit values in a
100x100 half-full array are now wasting 320K, which probably wouldn't
be eaten up by overhead in a sparse structure.

Just be sure that by using an alternate data structure you are not, in
fact, creating something even bigger than the original 2D array would
have been.

 

[Marcus]

Peter is right. The first question you have to ask is, "How big do I

expect this thing to be?"

Yep, that shoudl be the first question.

(_nothing_ is faster than a 2D array)

In my experience, accessing elements in matrix that is represented by a
1D array is usual faster than a 2D array C#. (comparing matrix[i*cols+j]
to matrix[i,j] or matrix[j]).

If you can exploit the fact that most elements are null or zero
(depending the data type), sparse matrices can outperform dense matrices
(so they can be faster and use less memory). For a trivial example, sum
all elements of a data matrix.

 

[Bruce Wood]

Yes, that's true. I was being sloppy. I should have said, "Finding an
specific element is fastest in a 2D array." Other operations such as
summing the elements may indeed be faster in a sparse structure.

I find it odd that a 1D array would "outperform" a 2D array. I would
expect them to perform exactly the same, as most languages use the 1D
implementation under the covers, so usually it's just a difference
between the language doing the math behind the scenes or you doing the
math in code. That experience, however, comes from C, so .NET may be
different.

 

[Duncan M Gunn]

Thanks for all the help. I need to do a bit of investigation to find out
likely data sizes and the number of zero entries that are likely, before I
decide on a storage structure. It seems unlikely I would gain any advantage
on computing summary values (this will already have been done) so therefore
space is my only other consideration.

Does anyone know if there exists a public domain C# (or C++/C)
implementation of a sparse matrix structure I could use?

 

[Dan Bass]

This shouldn't be hard to port:
http://www.codeproject.com/cpp/sparse_matrices.asp

 

[Marcus]

check out http://nmath.sourceforge.net/wiki/index.php/Main_Page

 

[Duncan M Gunn]

Thanks for your help, this will give me a good starting point if we require
to use such a structure.