首页 文章

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

提问于
浏览
9

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 回答

  • 7

    从理论上讲,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 表示空指针 .

    +---+---+---+---+
    |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不是很高,因此高速缓存未命中的数量非常少 .

  • 0

    如果查询操作要求告知至少一个已经在相关范围内的现有成员的值(可能是下限),则可以实现目标(O(1),O(1)和O(k)) ) . 您能否保证至少知道该系列的一名成员?我猜不会 . 如果可以,我会扩大 .

    我现在将重点放在指定的问题上 . 数据结构中的每个数字应构成链表的一部分,这样每个数字都知道数据结构中的下一个最大数字 . 在C.

    struct Number {
        struct Number *next_highest;
        int value;
    };
    

    显然,集合中的最大值将具有 next_highest==NULL ,否则 this->value < this->next_highest->value

    要添加,删除或查询,我们需要能够找到接近特定查找值的现有 Number .

    set<Number *, specialized_comparator_to_compare_on_value_t >
    

    插入和删除将是O(log(N)),并且查询将是O(log(N)k) . N是当前集合中的值的数量,正如您所说的,它将远小于M(相关数据类型的可能值的数量) . 因此log(N)<log(M) . 但在实践中,还应考虑其他方法,例如尝试和此类数据结构 .

相关问题