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

Question

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

目前，我正在使用 std::set （仅插入和迭代接口），这很不错，但仍然不够快。std::unordered_set 慢了一倍，与 Google Hash Maps 相同。我想知道针对这种情况优化了哪些数据结构？

Answer 1

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

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

如果您没有运行，但您往往会发现值分布不均，那么展开树可以降低访问最常用元素的成本。它通过使用靠近顶部的频繁元素创建一个故意不平衡的树来工作，就像霍夫曼代码一样。

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 hashing之前已经在 Stackoverflow 上讨论过，对于这么小的集合也可能是一个好方法。如果您真的需要优化速度，您可以在汇编器中实现散列函数和查找 - 在线性数据结构上这将非常简单，因此汇编器实现的编码和维护工作不应该过于难以维护。

Answer 4

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

Answer 5

随机数据结构可能非常适合您的工作。看一下跳过列表——尽管我不知道它的任何 C++ 实现。我打算向 Boost 提交一个，但一直没有时间去做。

Answer 6

可能是一个以b 树（而不是二叉树）作为内部数据结构的集合。我在实现这一点的 codeproject 上找到了这篇文章。

Answer 7

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

哪个操作对你来说很慢？你做更多的插入还是更多的迭代？

Answer 8

你有多少内存？32 位“仅”占用 4GB/8 字节，即 512MB，对于高端服务器来说并不多。这将使您的插入 O(1)。但这可能会使迭代变慢。尽管跳过所有只有零的单词会优化大多数迭代。如果您的 100 个数字在相对较小的范围内，您可以通过保持最小值和最大值来进一步优化。

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

Answer 9

由于没有人明确提到它，您是否考虑过内存局部性？具有导致页面错误的插入算法的真正出色的数据结构对您没有好处。实际上，带有仅导致缓存未命中的插入的数据结构可能对性能非常不利。

当插入碰撞太慢时，您是否确保将一组天真的无序元素打包在一个固定数组中，并通过简单的交换到前面？这是一个简单的实验，可能表明您存在内存局部性问题而不是算法问题。