How to best implement a 2D sparse array of data?

Question

To the more experienced C# programmers how do I do this best? I have a 2 dimensional mapping of values in a database which represent a random sampling of a somewhat round (but not exactly round) shape when drawn out on paper. That is the data is in the form of a row coordinate and a column coordinate and a data value for that set of coordinates. If this was a 100% sampling the data would look like a filled circle when plotted on paper. Since it is only a random sampling not all of the coordinates belonging to the filled circle will be present. Before I retrieve the data from the database I do not know the maximum value of either the row or column coordinate. I can know that first when I retrieve all the data from the database and find the maximum values for both coordinates. My question is what is the best way to store this data in my C# program? In a 2D rectangular array? This may be wasteful because the data is sparse. In an array of hashtables where the array key is the row coordinate and the hashtable key is the column coordinate? In an array list of sorted lists? Important is that I can access the value quickly for any combination of row and column coodinates as this will happen very often in the program. Thanks for any tips!

Jonathan Wood · Answer

There's a very simple one (not math-oriented) posted at http://www.blackbeltcoder.com/Articles/algorithms/creating-a-sparse-matrix-in-net .

steve · Answer

Thank you very much Alan! That is a very good introduction for me to the use of dictionaries. I can see its usage from your example! And I am sure I will definitely make good use of it in the future!

Alan · Answer

I thought I'd just clarify that a Dictionary is the generic equivalent of a Hashtable where both the key and value are strongly typed. In a Hashtable they are weakly typed because internally they are stored as type System.Object. This means that value types have to be boxed which is not good from a performance viewpoint. You can use any type you like for the keys as long as the keys are unique and (in the case of reference type) don't change in a way which affects the hash code. For future reference here's a very simple example of how this works in practice: using System; using System.Collections.Generic; using System.Drawing; class Test { static void Main() { Dictionary dict = new Dictionary (); dict.Add(new Point(100200) 300.3); dict.Add(new Point(150250) 400.5); Point key = new Point(100200); Console.WriteLine(The value for point {0} is {1} key dict[key]); key = new Point(150250); Console.WriteLine(The value for point {0} is {1} key dict[key]); Console.ReadKey(); } }

steve · Answer

Thank you for the reply. I need to look these things up in help since I am not used to using them. But it sounds like you mean I should use a hashtable but where the key is a point structure? Or am I confused? I did not think that the key of a hashtable could be something other than a number or a string. I have come up with a way of doing this which may be somewhat memory wasteful but makes the coding rather easy to read. What I actually have to store in 2D sparse arrays are two pieces of information per coordinate location: a chip type and an inspection value. The chip type is only mildly sparse (looks like a round disk in a rectangular field) and the inspection value can be very sparse depending on how many inspections of the chips were make. So I have defined a struct consisting of two int values for chip type and inspection value and I store the data after retrieval from the database in a rectangular array of these structs. The coding becomes rather easy because if my struct's members are called chiptype and inspectvalue and the 2D array is called chipmap then for a given xy coordinate pair I access the values with chipmap[xy].chiptype chipmap[xy].inspectvalue so I think I will go with this for now.

Alan · Answer

If you're using .NET 2.0 or later and the value is of type double then I'd be inclined to use a Dictionary . As each pair of coordinates is unique then a Point is suitable as a key. Rather than define your own Point type I'd just use the System.Drawing.Point struct. This is very lightweight and as it's a value type garbage collection is not a problem. Also it contains it's own implementation of the GetHashCode() method - which is used internally by the generic Dictionary class - and can be relied upon to be reasonably efficient particularly for sparse data even if it cannot be guaranteed that different Points won't produce the same hash. The Dictionary class contains code to deal with hash collisions in any case.