The implementation of a three-dimensional sparse matrix?

Question

I found a pretty good sparse matrix implementation for C # over http://www.blackbeltcoder.com/Articles/algorithms/creating-a-sparse-matrix-in-net .

But since I work in a 3d coordinate system, I need a sparse matrix implementation that I can use to display a 3d coordinate system.

Details: I store a large amount of data of primitive shapes in memory, such as cubes. I have a large number of them (about 30 million), and I have a lot of zero (zero) records. Given that each of my records costs 1 byte of input, I would like to implement a sparse matrix so that I can save enough memory space.

Note. Quick access to the matrix cells is quite an important factor for me, so I would trade in speed compared to memory consumption.

Answer 1

The very simple solution I just made is this:

public class Sparse3DMatrix<T> { Dictionary<Tuple<int,int,int>, T> values = new Dictionary<Tuple<int, int, int>, T>(); public T this[int x, int y, int z] { get { return values[new Tuple<int, int, int>(x, y, z)]; } set { values[new Tuple<int, int, int>(x, y, z)] = value; } } public bool ContainsKey(int x, int y, int z) { return values.ContainsKey(new Tuple<int, int, int>(x, y, z)); } } 

using:

 var test = new Sparse3DMatrix<float>(); test[1, 1, 1] = 1f; Console.WriteLine(test[1, 1, 1]); 

It can be expanded using methods similar to those that its version has, and with checks for x, y, z , etc.

I'm sure someone can say something about its performance. This will be a decent implementation if you really don't need something for high performance. It depends on the implementation of the Tuple hash code and your specific use. If we assume that the hashes are good, we will have O(1) search time. If you know that you will have many elements, you can use new Dictionary<...>(initial capacity) to avoid unnecessary resizing when adding elements.

Unlike him, this has only one Dictionary with all the elements. Its version has dictionaries of dictionaries. Its advantage, if you need to scan the entire row, you can simply repeat the second-level dictionary (this will not help you if you want to scan columns), which is faster than an individual element search. But having one dictionary means less memory - especially when you have few items in a row.

Answer 2

Lasse Espeholt's solution is practical, but can be improved by removing items when they are “zeroed out” or zeroed out. If you do not make this matrix or array, you can lose sparseness. Here is an alternative solution that assumes if an element of some type has not been inserted, that it is the default value of that type. For example, for double , which means 0.0, and for string , which means null .

 public class Sparse3DArray<T> { private Dictionary<Tuple<int, int, int>, T> data = new Dictionary<Tuple<int, int, int>, T>(); public int Nnz { get { return data.Count; } } public T this[int x, int y, int z] { get { var key = new Tuple<int, int, int>(x, y, z); T value; data.TryGetValue(key, out value); return value; } set { var key = new Tuple<int, int, int>(x, y, z); if (null == value) data.Remove(key); else if (value.Equals(default(T))) data.Remove(key); else data[key] = value; } } } 

Answer 3

The fact that you are working in a three-dimensional coordinate system does not change whether you can use this data structure. A matrix for three-dimensional space may be contained using a sparse matrix, the same as a 2D matrix; these are just records that are changing.

You would use a sparse matrix for large matrices with lots of null entries. This is typical of discrete notions of physics problems that come from finite difference methods and finite elements. They have strips of nonzero elements grouped diagonally; entries outside the diagonal strip are usually zero. A rare matrix will not save them; decompositions, such as LU and QR, must be written to know how to deal with resolution.

These matrices can describe problems in 2D or 3D spaces.

I believe you are wrong if you think you need a different data structure.

Answer 4

Why not use a KD-Tree or similar data structure (like Octtree)? There are large C ++ implementations, for example: FLANN