449,437 Members | 1,599 Online Need help? Post your question and get tips & solutions from a community of 449,437 IT Pros & Developers. It's quick & easy.

# Matrix storage structure

 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 Nov 16 '05 #1
10 Replies

 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" 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 Nov 16 '05 #2

 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 Nov 16 '05 #3

 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" 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 Nov 16 '05 #4

 P: n/a 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. :) Nov 16 '05 #5

 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 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. :) Nov 16 '05 #6

 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. Nov 16 '05 #7

 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" 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. Nov 16 '05 #8

 P: n/a This shouldn't be hard to port: http://www.codeproject.com/cpp/sparse_matrices.asp "Duncan M Gunn" 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" 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. Nov 16 '05 #9

 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" wrote in message news:11**********************@z14g2000cwz.googlegr oups.com...Yes, that's true. I was being sloppy. I should have said, "Finding anspecific element is fastest in a 2D array." Other operations such assumming the elements may indeed be faster in a sparse structure.I find it odd that a 1D array would "outperform" a 2D array. I wouldexpect them to perform exactly the same, as most languages use the 1Dimplementation under the covers, so usually it's just a differencebetween the language doing the math behind the scenes or you doing themath in code. That experience, however, comes from C, so .NET may bedifferent. Nov 16 '05 #10

 P: n/a Thanks for your help, this will give me a good starting point if we require to use such a structure. Nov 16 '05 #11

### This discussion thread is closed

Replies have been disabled for this discussion. 