algorithm - 构建和查找整数范围集的数据结构

Question

我有一组 uint32 整数，集合中可能有数百万个项目。其中 50-70% 是连续的，但在输入流中它们以不可预测的顺序出现。

我需要:

1. 将此集合压缩到范围内以实现空间高效表示。已经使用简单的算法实现了这一点，因为只计算一次速度的范围在这里并不重要。经过此转换后的结果范围数量通常在 5 000-10 000 个范围内，当然其中许多是单项。

2. 测试某个整数的成员资格，不需要有关集合中特定范围的信息。这个必须非常快——O(1)。在想minimal perfect hash functions ，但它们不能很好地处理范围。 Bitsets空间效率非常低。其他结构，如二叉树，复杂度为 O(log n)，最糟糕的是它们的实现会产生许多条件跳转，处理器无法很好地预测它们，从而导致性能不佳。

是否有专门针对整数范围的数据结构或算法来解决此任务？

Answer 1

关于第二个问题:

您可以在 Bloom Filters 上查找. Bloom Filters 专门设计用于在 O(1) 中回答成员资格问题，尽管响应是 no 或 maybe(不像是/否那样明确:p).

在 maybe 的情况下，当然，您需要进一步处理才能真正回答问题(除非您的情况下概率答案就足够了)，但即使如此，Bloom Filter 也可能充当门keeper，并直接拒绝大多数查询。

此外，您可能希望在不同的结构中保留实际范围和退化范围(单个元素)。

• 最好将单个元素存储在哈希表中
• 实际范围可以存储在排序数组中

这减少了排序数组中存储的元素数量，因此减少了在那里执行的二分查找的复杂性。既然你说许多范围是退化的，我认为你只有大约 500-1000 个范围(即少一个数量级)，并且 log(1000) ~ 10

因此，我建议采取以下步骤:

• 布隆过滤器:如果没有，停止
• 真实范围的排序数组:如果是，停止
• 单个元素的哈希表

首先执行排序数组测试，因为根据您给出的数字(数百万个数字合并在几千个范围内)如果包含一个数字，它很可能在一个范围内而不是单个 :)

最后一点:当心 O(1)，虽然它看起来很有吸引力，但您并不是在渐近情况下。几乎没有 5000-10000 的范围，因为 log(10000) 大约是 13。所以不要通过获得具有如此高常数因子的 O(1) 解决方案来悲观你的实现，它实际上运行得比 O(log N ) 解决方案:)