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
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..
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With