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? (Links go to the MSDN reference pages.)

Dictionary<Tuple<int,int,int,int>> dict;

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

struct Index
{
    public readonly int First;
    public readonly int Second;
    public readonly int Third;
    public readonly int Fourth;
    ...
}

Dictionary<Index> dict;

Answer 2

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

Answer 3

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

Answer 4

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;

Answer 5

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.