代码之家  ›  专栏  ›  技术社区  ›  thr

以C#/最快的方式实现稀疏数组,将整数映射到特定的bucket/range数

  •  10
  • thr  · 技术社区  · 14 年前

    我的第一个问题是我需要在C#中实现一个非常快速的稀疏数组。最初的想法是使用一个正常的 Dictionary<uint, TValue> 把它包在我自己的类中,只露出 TValue 类型参数。结果这很慢。

    所以我的下一个想法是把每个整数映射到需要的范围内( UInt32.MinValue UInt32.MaxValue )到一个水桶里,一定的尺寸,然后用它。所以我在寻找一种很好的方法将无符号整数X映射到bucket Y,例如:

    将数字0-1023映射到8个不同的存储桶,每个存储桶包含128个数字,即0-127、128-255。

    2 回复  |  直到 14 年前
        1
  •  6
  •   Timwi    14 年前

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

    注意事项/缺点:

    • 64位(键为 无符号长整型 )是泛型,但另一个(键是 无符号整型 )假设 int 价值观,因为这是我当时所需要的;我相信你可以很容易地使这个通用。

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

        2
  •  4
  •   Loofer    12 年前

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

    • 数组中将有多少项
    • 这些项目是如何聚集在一起的
    • 空间/速度贸易

    大多数教科书都有一个关于稀疏数组的章节,只要做一个Google就会得到很多点击率。然后你就得把代码翻译成C#,或者直接用别人写的代码,我不费吹灰之力就找到了两个(我不知道它们有多好)