我有一组uint32整数，这组中可能有数百万个项目。它们中的50-70％是连续的，但在输入流中它们以不可预测的顺序出现。
uint32
我需要：
将此集合压缩到范围内以实现空间高效的表示。由于仅计算一次速度的范围在此并不重要，因此已经使用平凡的算法实现了这一点。经过这种转换后，生成的范围数通常在5000至10000之间，当然，其中许多都是单项的。
测试某些整数的成员资格，不需要有关集合中特定范围的信息。这一步必须非常快-O（1）。正在考虑最小的完美哈希函数，但它们不能很好地与范围配合使用。位集空间利用率非常低。其他结构（例如二叉树）的复杂度为O（log n），最糟糕的情况是实现会产生许多条件跳转，并且处理器无法很好地预测它们，从而导致性能下降。
是否有专门用于整数范围的数据结构或算法来解决此任务？
关于第二个问题：
您可以在Bloom Filters上查找。布隆过滤器是专门为回答O（1）中的隶属关系问题而设计的，尽管响应是no或maybe（（不是像yes / no：p那样明确）。
no
maybe
maybe当然，在这种情况下，您需要进一步处理才能真正回答问题（除非在您的情况下概率回答就足够了），但是即使如此，Bloom Filter仍可以充当网守，并直接拒绝大多数查询。
另外，您可能希望将实际范围和简并范围（单个元素）保留在不同的结构中。
这减少了存储在排序数组中的元素的数量，从而减少了在那里执行二进制搜索的复杂性。由于您声明许多范围退化，因此我认为您只有500-1000个范围（即小一个数量级），并且log（1000）〜10
因此，我建议采取以下步骤：
首先执行“排序数组”测试，因为从您给出的数字（数以千计的数字合并到数千个范围中）中，如果包含一个数字，则它有可能在一个范围内，而不是单个:)
最后一点：当心O（1），虽然看起来很吸引人，但您并非处于渐近状态。很少有5000-10000的范围，因为log（10000）类似于13。因此，不要通过获得常数因数如此高而实际上比O（log N慢）的O（1）解决方案来悲观您的实现）解决方案:)
