用于在稀疏域中设置位并迭代的快速容器（C++）？

Question

我需要一个只有两个操作的快速容器。从非常稀疏的域插入密钥（所有 32 位整数，大约 10 位）100 个在给定时间设置），并迭代插入的键。它应该处理 很多 命中相同条目的插入（例如 500k，但只有 100 个不同的条目）。

目前，我正在使用 std::set （仅插入和迭代接口），这很不错，但仍然不够快。std::unordered_set 慢两倍，Google 哈希映射也是如此。我想知道针对这种情况优化了什么数据结构？

Answer 1

根据输入的分布情况，您可以在不改变结构的情况下获得一些改进。

如果您倾向于获得大量单个值的运行，那么您可以通过保留已插入的最后一个值的记录来加速插入，并且如果匹配则不要打扰插入。每次输入需要额外的比较，但是在第一次运行之后的运行中保存每个元素的查找。因此，无论您使用何种数据结构，它都可以改善事物，具体取决于重复的频率以及比较与插入的相对成本。

如果你没有运行，但是你倾向于发现值不是均匀分布的，那么splay树使得访问最常用的元素更便宜。它的工作原理是创建一个故意不平衡的树，其中频繁的元素靠近顶部，就像霍夫曼代码一样。

Answer 2

我不确定我理解<！>“很多插入了相同条目<！>”的插入。你的意思是只有100个值是永远的成员，但500k大多数是重复的操作，插入这100个值中的一个？

如果是这样，那么我猜想最快的容器是在这100个值上生成无冲突的哈希值，然后维护一个数组（或向量）的标志（int或bit，根据什么效果最快）在您的架构上。）

我留下生成哈希作为读者的练习，因为我知道这是一种技术存在，但我自己从未研究过。关键是要在尽可能小的范围内获得快速哈希，这样对于100个值中的每个n，m，hash（n）！= hash（m）。

因此插入看起来像array[hash(value)] = 1;，删除看起来像array[hash(value)] = 0;（虽然你不需要），并枚举你遍历数组，并且对于索引n处的每个设置值，inverse_hash（n）是在你的收藏中。对于小范围，您可以轻松维护查找表以执行反向散列，或者不是扫描整个数组以查找设置标志，而是可以依次检查100个可能的值。

很抱歉，如果我误解了这种情况，这对你没用。说实话，它并不比常规散列表快得多，因为实际上对于100个值，您可以轻松调整表的大小，以便几乎没有碰撞，而不会使用如此多的内存来吹嘘缓存。

Answer 3

对于预期会很小的正在使用的集合，非拼写的哈希表可能没问题。如果你可以忍受偶尔的扩展操作，如果它超过70％已满，则以2的幂增长。 Cuckoo哈希已经之前在Stackoverflow上讨论过，也可能是一个很好的方法。如果你真的需要优化速度，你可以实现散列函数和汇编程序查找 - 在线性数据结构上这将非常简单，因此汇编程序实现的编码和维护工作不应该过度难以维护。

Answer 4

您可能需要考虑实施 哈希树 在每个级别使用以 10 为基数的哈希函数而不是二进制哈希函数。您可以将其设置为非存储桶，在这种情况下，您的性​​能将是确定性的 (log10)，或者根据您的预期分布调整存储桶大小，以便您只有几个键/存储桶。

Answer 5

随机数据结构可能非常适合您的工作。请查看跳过列表 <！>＃8211;虽然我不知道它的任何decend C ++实现。我打算向Boost提交一个，但从来没有去做过。

Answer 6

也许有一个 b-tree （而不是二叉树）的集合内部数据结构。我在codeproject上发现了这篇文章，该文章实现了这一点。

Answer 7

请注意，虽然插入哈希表的速度很快，但迭代它并不是特别快，因为你需要遍历整个数组。

哪种操作对你来说很慢？你做了更多的插入或更多的迭代吗？

Answer 8

你有多少记忆？ 32位取<！>“;仅<！>”; 4GB / 8字节，达到512MB，对于高端服务器来说并不多。这会使你的插入O（1）。但这可能会使迭代变慢。虽然仅使用零跳过所有单词会优化大多数迭代。如果你的100个数字在一个相对较小的范围内，你可以通过保持最小值和最大值来进一步优化。

我知道这只是蛮力，但有时候蛮力就足够了。

Answer 9

由于没有人明确提到它，你有没有想过内存局部性？一个非常好的数据结构，带有导致页面错误的插入算法对你没有好处。实际上，带有插件的数据结构只会导致高速缓存未命中，这对于perf来说可能非常糟糕。

你确定一个天真的无序元素包装在一个固定的数组中，当一个插入的collisides太慢时，它与前面的简单交换？它是一个简单的实验，可能会显示您有内存局部性问题而不是算法问题。