Implementation of extremely sparse arrays

I have an extremely sparse static array with 4 dimensi开发者_如何学运维ons 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

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>();

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..

Use hashtable (generic Dictionary is already implemented as Hashtable). As key use vector of 4 dimension index. As value store what you want.

What I'd do is use hash lists instead of "normal" arrays for this, then (pseudo-code):

// first, check bounds:
if(x < 0 || y < 0 || z < 0 || w < 0
|| x > xsize || y > ysize || z > zsize || w > wsize)
    throw new Whatever(...);

// now return value if != 0
if(x in arr && y in arr[x] && z in arr[x][y] && w in arr[x][y][z])
    return arr[x][y][z][w];
else
    return 0;

I think the best way is to use a hash-table (Dictionary<T, int>), indexed with a custom struct containing the 4 indexes. Don't forgot to override object.Equals() and object.GetHashCode() on that struct.