known range 中有一个任意数量的 distinct 无符号整数值 .
The number of integer values is << the number of integers within the range.
我想构建一个允许以下运行时复杂性的数据结构:
-
插入O(1)
-
插入完成后:
-
删除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
这样的数据结构是否可能? (借助查询表等)?
An approximation 我想到的是:
-
将插入的值插入桶中 . 0..31 =>桶0,32..63 =>桶1,64..95 =>桶2,96..127 =>桶3,...
-
插入:使用简单的移位算法查找存储桶ID,然后将其插入每个存储桶的数组中
-
查找:使用移位算法查找start和endpoint的bucket id . 查看第一个和最后一个存储桶中的所有值,并检查它们是否在范围内或范围之外 . 将所有中间桶中的所有值添加到搜索结果中
-
删除:使用shift查找存储桶ID . 使用存储桶中的最后一个值切换要删除的值,然后减少此存储桶的计数 .
缺点:如果有许多查询查询范围小于32的值,则每次都会搜索整个存储桶 .
下侧2:如果范围内有空桶,则在搜索阶段也会访问它们 .
2 回答
从理论上讲,van Emde Boas树是你最好的选择,使用O(log log M)时间操作,其中M是范围的大小 . 虽然有更高效的变体,但空间使用量非常大 .
实际上,Mortensen,Pagh和Patrascu在论文_2525894中描述了理论上的现有技术 .
我不确定现有的下限是否排除O(1),但是M不会大到足以使区分成为问题 . 而不是vEB结构,我只使用k-ary trie,k为2或2的幂,如32或64 .
编辑:这是用trie进行范围搜索的一种方法 .
让's assume each datum is a bit pattern (easy enough; that' s CPU如何看待它) . 每个子树由具有特定前缀的所有节点组成 . 例如,{0000,0011,0101,1001}由以下4-ary trie表示,其中
X
表示空指针 .一对夫妇的优化很快就会显现出来 . 首先,如果所有的位模式都是相同的长度,那么我们不需要将它们存储在叶子上 - 它们可以从下降路径重建 . 我们所需要的只是位图,如果k是机器字中的位数,那么就可以很好地适应前一级指针的位置 .
为了在trie中搜索类似[0001,1000]的范围,我们从根开始,确定哪些子树可能与范围相交并递归它们 . 在该示例中,根的相关子节点是00,01和10. 00的相关子节点是表示前缀0001,0010和0011的子树 .
对于k固定,来自k-ary trie的报告是O(log M s),其中M是位模式的数量,s是命中数 . 不要被愚弄 - 当k为中等时,每个节点占用一对高速缓存行,但是trie不是很高,因此高速缓存未命中的数量非常少 .
如果查询操作要求告知至少一个已经在相关范围内的现有成员的值(可能是下限),则可以实现目标(O(1),O(1)和O(k)) ) . 您能否保证至少知道该系列的一名成员?我猜不会 . 如果可以,我会扩大 .
我现在将重点放在指定的问题上 . 数据结构中的每个数字应构成链表的一部分,这样每个数字都知道数据结构中的下一个最大数字 . 在C.
显然,集合中的最大值将具有
next_highest==NULL
,否则this->value < this->next_highest->value
要添加,删除或查询,我们需要能够找到接近特定查找值的现有
Number
.插入和删除将是O(log(N)),并且查询将是O(log(N)k) . N是当前集合中的值的数量,正如您所说的,它将远小于M(相关数据类型的可能值的数量) . 因此log(N)<log(M) . 但在实践中,还应考虑其他方法,例如尝试和此类数据结构 .