Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
1.1k views
in Technique[技术] by (71.8m points)

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

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.

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

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:

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


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...