Sparse Multidimensional Array or Matrix Libraries in .NET

Question

I have a need for a sparse matrix in up to 4 dimensions in a .NET application. The size of the matrix (if represented as a .NET Array) would potentially top 400MB.

The array is likely to be very sparse, and I need to be able to instantiate and dispose it very quickly (although that's not a no go). I'm therefore after a sparse array library, consumable from .NET 3.5 (which I believe rules out using BGL from Managed C++?) that is as dense as possible as I can get and the supports fast random access indexing. It must be serializable to some dense format that can be inexpensively cached.

Does such a thing exist (yet) for .NET? FOSS? Mature?

TIA

Andrew Matthews

Answer 1

It is fairly simple to implement your own with a Dictionary. The implementation below works for 2 dimensions but you can easily implement 3 or 4 dimensions. The storage is very efficient when the matrix is sparse. It is not a good implementation if you plan to add or remove columns frequently.

class SparseMatrix<T>
    {
        public T this[int i, int j]
        {
            get
            {
                T result;
                if (!_data.TryGetValue(new Key(i, j), out result))
                    return default(T);
                return result;
            }
            set { _data[new Key(i, j)] = value; } // Could remove values if value == default(T)
        }

        private struct Key
        {
            public Key(int i, int j)
            {
                _i = i;
                _j = j;
            }

            private readonly int _i;    
            private readonly int _j;
            public override bool Equals(object obj)
            {
                if (!(obj is Key))
                    return false;
                var k = (Key) obj;
                return k._i == _i && k._j == _j;
            }

            public override int GetHashCode()
            {
                return _i << 16 + _j; // Could be smarter based on the distribution of i and j
            }


        }

        private readonly Dictionary<Key, T> _data = new Dictionary<Key, T>();
    }