act*_*ual 6 algorithm integer range set data-structures
我有一组uint32整数,集合中可能有数百万个项目.其中50-70%是连续的,但在输入流中它们以不可预测的顺序出现.
我需要:
将此集合压缩到范围内以实现空间有效表示.已经使用普通算法实现了这一点,因为只计算一次速度的范围在这里并不重要.在此转换之后,所得范围的数量通常在5 000-10 000之间,当然,其中许多是单项.
测试某些整数的成员资格,不需要有关集合中特定范围的信息.这个必须非常快 - O(1).正在考虑最小的完美哈希函数,但它们不能很好地适应范围.位集空间效率很低.其他结构,如二叉树,具有O(log n)的复杂性,最糟糕的是它们实现了许多条件跳转,而处理器无法很好地预测它们,从而导致性能不佳.
是否有专门用于整数范围的数据结构或算法来解决此任务？
Mat*_* M. 11
关于第二个问题:
你可以查看Bloom Filters.布隆过滤器专门用于回答O(1)中的成员问题,尽管响应是no或者maybe(不像是/否那样明确:p).
maybe当然,在这种情况下,您需要进一步处理以实际回答问题(除非您的情况下概率答案已足够),但即便如此,布隆过滤器也可能充当守门员,并且完全拒绝大多数查询.
此外,您可能希望在不同结构中保留实际范围和退化范围(单个元素).
这减少了存储在排序数组中的元素数量,从而减少了在那里执行的二进制搜索的复杂性.由于你声明许多范围是退化的,我认为你只有500-1000个范围(即,一个数量级减少),并且log(1000)~10
因此,我建议采取以下步骤:
排序阵列测试首先执行,因为如果包含一个数字,你给出的数字(在几千个范围内合并的数百万个数字),它可能在一个范围而不是单个:)
最后一个注意事项:提防O(1),虽然看起来很吸引人,但你不是在渐近的情况下.只有5000-10000的范围很少,因为log(10000)就像13那样.所以不要通过获得具有如此高的常数因子的O(1)解决方案来使你的实现失望,它实际上比O(log N)运行得慢. )解决方案:)
如果您事先知道范围是什么,那么您可以使用下面概述的策略检查给定整数是否存在于O(lg n)中的一个范围内.它不是O(1),但在实践中它仍然很快.
这种方法背后的想法是,如果你将所有范围合并在一起,你就会在数字线上有一系列不相交的范围.从那里,您可以通过说区间[a,b]≤[c,d] iffb≤c来定义这些区间的排序.这是一个总排序,因为所有范围都是不相交的.因此,您可以将所有间隔放在一起形成静态数组,然后按此顺序对它们进行排序.这意味着最左边的间隔位于数组的第一个插槽中,最右边的间隔位于最右边的插槽中.这种结构需要O(n lg n)时间.
要检查某个间隔是否包含给定的整数,可以对此数组执行二进制搜索.从中间间隔开始,检查该间隔中是否包含整数.如果是这样,你就完成了.否则,如果该值小于范围中的最小值,则继续左侧的搜索,如果该值大于该范围中的最大值,则继续右侧的搜索.这本质上是一个标准的二进制搜索,它应该在O(lg n)时间内运行.
希望这可以帮助!