P: n/a

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  
Share this Question
P: n/a

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.
"Duncan M Gunn" <gu***@gaelqualityNOSPAM.co.uk> wrote in message
news:uS**************@TK2MSFTNGP15.phx.gbl... 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  
P: n/a

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
Duncan M Gunn wrote: 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  
P: n/a

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
"Duncan M Gunn" <gu***@gaelqualityNOSPAM.co.uk> wrote in message
news:uS**************@TK2MSFTNGP15.phx.gbl... 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  
P: n/a

Peter is right. The first question you have to ask is, "How big do I
expect this thing to be?"
Any sparsematrix 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 halffull array, even of 64bit 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 64bit values in a
100x100 halffull 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. :)  
P: n/a

> 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[i][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 wrote: Peter is right. The first question you have to ask is, "How big do I expect this thing to be?"
Any sparsematrix 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 halffull array, even of 64bit 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 64bit values in a 100x100 halffull 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. :)  
P: n/a

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.  
P: n/a

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?
"Bruce Wood" <br*******@canada.com> wrote in message
news:11**********************@z14g2000cwz.googlegr oups.com... 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.  
P: n/a

This shouldn't be hard to port: http://www.codeproject.com/cpp/sparse_matrices.asp
"Duncan M Gunn" <gu***@gaelqualityNOSPAM.co.uk> wrote in message
news:e0**************@TK2MSFTNGP09.phx.gbl... 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?
"Bruce Wood" <br*******@canada.com> wrote in message news:11**********************@z14g2000cwz.googlegr oups.com... 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.
 
P: n/a

check out http://nmath.sourceforge.net/wiki/index.php/Main_Page
Duncan M Gunn wrote: 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?
"Bruce Wood" <br*******@canada.com> wrote in message news:11**********************@z14g2000cwz.googlegr oups.com...
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.  
P: n/a

Thanks for your help, this will give me a good starting point if we require
to use such a structure.   This discussion thread is closed Replies have been disabled for this discussion.   Question stats  viewed: 7394
 replies: 10
 date asked: Nov 16 '05
