以C#/最快的方式实现稀疏数组,将整数映射到特定的桶/范围号

Question

我最初的问题是我需要在C#中实现一个非常快速的稀疏数组.最初的想法是使用法线Dictionary<uint, TValue>并将其包装在我自己的类中以仅显示TValue类型参数.事实证明这很慢.

所以我的下一个想法是将所需范围(UInt32.MinValueto UInt32.MaxValue)中的每个整数映射到某个大小的存储桶并使用它.所以我正在寻找一种将无符号整数X映射到桶Y的好方法,例如:

将数字0-1023映射到8个不同的桶,每个桶包含128个数字,0-127,128-255.

但是,如果某人有更好的方法在C#中实现快速稀疏数组,那么这也是最受欢迎的.

Answer 1

我也注意到,Dictionary<K,V>当键是整数时,它很慢.我不确切知道为什么会这样,但我为uint和ulong键写了一个更快的哈希表实现:

• Efficient32bitHashTable和Efficient64bitHashTable

注意事项/缺点:

• 64位(密钥是ulong)是通用的,但另一个(密钥是uint)假设int值,因为这是我当时所需的全部内容; 我相信你可以很容易地制作这个通用的.

• 目前,容量永远确定哈希表的大小(即它不会增长).

Answer 2

有 101 种不同的方法来实现稀疏数组，具体取决于以下因素：

• 数组中有多少项
• 项目如何聚集在一起
• 空间/速度贸易
• ETC

大多数教科书都有关于稀疏数组的章节，只需谷歌一下就会出现很多点击。然后你必须将代码翻译成C#，或者只是使用别人写的代码，我毫不费力地找到了两个（我不知道这些有多好）

• 使用专用数组来加速您的代码
• 用于 C# 的 SparseArray