Implementing a sparse array in C# / fastest way to map integer to a specific bucket/range number.

Question

My initial problem is that I need to implement a very fast, sparse array in C#. Original idea was to use a normal Dictionary<uint, TValue> and wrap it in my own class to only expose the TValue type parameter. Turns out this is pretty slow.

So my next idea was to map each integer in the needed range (UInt32.MinValue to UInt32.MaxValue) to a bucket, of some size and use that. So I'm looking for a good way to map an unsigned integer X to a bucket Y, for example:

Mapping the numbers 0-1023 to 8 different buckets holding 128 numbers each, 0-127, 128-255.

But if someone has a better way of implementing a fast sparse array in C#, that would be most appreciated also.

Answer 1

There are a 101 different ways to implement sparse arrays depending on factors like:

• How many items will be in the array
• How are the items clustered together
• Space / speed trade of
• etc

Most text books have a section on sparse array, just doing a Google comes up with lots of hits. You will then have to translate the code into C# that is not hart.

Or just use the code someone else has written, I have found two without much efort (I don't know how good thes are)

• Use Specialty Arrays to Accelerate Your Code
• SparseArray for C#

Answer 2

I, too, noticed that Dictionary<K,V> is slow when the key is an integer. I don’t know exactly why this is the case, but I wrote a faster hash-table implementation for uint and ulong keys:

• Efficient32bitHashTable and Efficient64bitHashTable

Caveats/downsides:

• The 64-bit one (key is ulong) is generic, but the other one (key is uint) assumes int values because that’s all I needed at the time; I’m sure you can make this generic easily.

• Currently the capacity determines the size of the hashtable forever (i.e. it doesn’t grow).