Implementation of extremely rare arrays

Question

I have a very rare static array with 4 sizes of 8192 each, which I want to perform searches (C #). Only 68796 of these 4.5 * 10 ^ 15 values ​​are nonzero. What is the fastest way to do this, while speed and low memory usage are vital?

thanks

Answer 1

First, I would say that simple arrays clearly represent the wrong data structure for your problem.

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

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

I never did this myself, but it should work fine. If you do not have a ready-made Tuple because you are working with a version of the .NET Framework prior to .NET 4, you can specify 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 can use a simple Dictionary or create a similar map that suits your needs (it will be an array in which you place the elements according to the hash value that you calculate from your 4 values), but you will need to take care of the collision.

Also a binary tree tree can do the trick if you accept the logarithmic complexity for the search.

Answer 3

Using hashtable (a generic dictionary is already implemented as a hashtable). As a key vector for using a 4-dimensional index. How value preserves what you want.

Answer 4

What I would 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 struct containing 4 indexes. Remember to override object.Equals() and object.GetHashCode() on this struct .