用于在查询范围内有效查找整数的数据结构

Question

在已知范围内存在任意数量的不同无符号整数值.

整数值的数量是<<范围内的整数数.

我想构建一个允许以下运行时复杂性的数据结构:

1. 插入O(1)
2. 插入完成后:
   • 删除O(1)
   • 获取O(k)中查询范围内的所有值,其中k是结果值的数量(不必对返回值进行排序)

内存复杂性不受限制.但是,天文数量太大的内存不可用;-)

这是一个例子:

• range = [0,1023]
• 插入42
• 插入350
• 插入729
• 插入64
• 插入1
• 插入680
• 插入258
• 在[300; 800]中找到值; 返回{350,729,680}
• 删除350
• 删除680
• 在[35; 1000]中找到值; 返回{42,258,64,729,258}
• 删除42
• 删除258
• 找到[0; 5]; 返回{1}
• 删除1

这样的数据结构是否可能？(借助查询表等)？

我想到的近似值是:

• 将插入的值插入桶中.0..31 =>桶0,32..63 =>桶1,64..95 =>桶2,96..127 =>桶3,...

• 插入:使用简单的移位算法查找存储桶ID,然后将其插入每个存储桶的数组中

• 查找:使用移位算法查找start和endpoint的bucket id.查看第一个和最后一个存储桶中的所有值,并检查它们是否在范围内或范围之外.将所有中间桶中的所有值添加到搜索结果中

• 删除:使用shift查找存储桶ID.使用存储桶中的最后一个值切换要删除的值,然后减少此存储桶的计数.

缺点:如果有许多查询查询范围小于32的值,则每次都会搜索整个存储桶.

下侧2:如果范围内有空桶,则在搜索阶段也会访问它们.

Answer 1

从理论上讲,van Emde Boas树是你最好的选择,使用O(log log M)时间操作,其中M是范围的大小.虽然有更高效的变体,但空间使用量非常大.

实际上,Mortensen,Pagh和Patrascu撰写的论文" On Dime Reporting in One Dimension"中描述了理论上的现有技术.

我不确定现有的下限是否排除O(1),但是M不会大到足以使区分成为问题.而不是vEB结构,我只会使用k-ary trie,其中ka的功率为32或64.

编辑:这是用trie进行范围搜索的一种方法.

让我们假设每个数据都是一个位模式(很容易;这就是CPU对它的看法).每个子树由具有特定前缀的所有节点组成.例如,{0000,0011,0101,1001}由以下4-ary trie X表示,其中表示空指针.

+---+---+---+---+
|00\|01\|10\|11X|
+--|+--|+--|+---+
   |   |   |
   |   |   +----------------------------+
+--+   |                                |
|      +------------+                   |
|                   |                   |
v                   v                   v
+---+---+---+---+   +---+---+---+---+   +---+---+---+---+
|00\|01X|10X|11\|   |00X|01\|10X|11X|   |00X|01\|10X|11X|
+--|+---+---+--|+   +---+--|+---+---+   +---+--|+---+---+
   |           |           |                   |
   v           v           v                   v
  0000        0011        0101                1001

一对夫妇的优化很快就会显现出来.首先,如果所有的位模式都是相同的长度,那么我们不需要将它们存储在叶子上 - 它们可以从下降路径重建.我们所需要的只是位图,如果k是机器字中的位数,那么就可以很好地适应前一级指针的位置.

+--------+--------+--------+--------+
|00(1001)|01(0100)|10(0100)|11(0000)|
+--------+--------+--------+--------+

为了在trie中搜索类似[0001,1000]的范围,我们从根开始,确定哪些子树可能与范围相交并递归它们.在该示例中,根的相关子节点是00,01和10. 00的相关子节点是表示前缀0001,0010和0011的子树.

对于k固定,来自k-ary trie的报告是O(log M + s),其中M是位模式的数量,s是命中数.不要被愚弄 - 当k为中等时,每个节点占用一对高速缓存行,但是trie不是很高,因此高速缓存未命中的数量非常少.