Implementation of extremely sparse arrays

Question

I have an extremely sparse static array with 4 dimensions of 8192 each that I want to do lookups from (C#). Only 68796 of these 4.5 * 10^15 values are non-zero. What is the fastest way to do this, with speed and low memory usage being vital?

Thanks

Answer 1

First, I would argue that plain arrays are quite clearly the wrong kind of data structure for your problem.

How about using a dictionary where you use a 4-tuple as index?

var lookup = new Dictionary<Tuple<int,int,int,int>, int>();

I've never done that myself, but it should work fine. If you don't have Tuple ready because you're working with a version of the .NET Framework preceding .NET 4, you could provide your own index type:

struct LookupKey
{
    public readonly int First;
    public readonly int Second;
    public readonly int Third;
    public readonly int Fourth;
    …
}

var lookup = new Dictionary<LookupKey, int>();

Answer 2

You could use a plain Dictionary or create a similar map suited for your needs (it will be an array in which you place elements according to an hashvalue you calculate on your 4 values) but you'll need to care about collisions.

Also a binary seach tree can make the trick if you accept a logarithmic complexity for lookup..