Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Implementation of extremely sparse arrays

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

like image 364
Hassan Avatar asked Oct 24 '10 13:10

Hassan


2 Answers

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>();
like image 160
stakx - no longer contributing Avatar answered Sep 21 '22 02:09

stakx - no longer contributing


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

like image 23
Jack Avatar answered Sep 22 '22 02:09

Jack