具有 O(log n) indexOf 操作的列表

Question

我正在寻找一种数据结构，它可以存储元素列表，同时还可以在给定元素和给定索引的元素的情况下对索引进行子O(n)查找，以及插入指数.

元素密集（整数 0..n）且唯一，但未排序。

例如，在 Rust 中，这个数据结构可以这样使用：

fn main() {
    let mut list = List::new();
    list.extend(vec![5, 2, 0, 4, 1, 3]);

    assert_eq!(list.get(2), 0);
    assert_eq!(list.get(3), 4);
    assert_eq!(list.index_of(0), 2);
    assert_eq!(list.index_of(4), 3);
}

O(√n) 操作是可以接受的，O(log n) 是理想的。我在这里画一个空白；非常感谢任何帮助！

Answer 1

单独维护 Vec<T> 和 HashMap<usize, T> 是否足够？ HashMap 的 lower lookup time 比 O(log n) 的 O(1)~.

这样做的缺点似乎是：

您必须将 Vec<T> 和 HashMap<usize, T> 都存储在内存中。
删除元素后，您还必须减少 HashMap<usize, T> 中每个元素的索引，这可能会使删除成本很高。

use std::collections::HashMap;

struct List {
    index_to_value: Vec<i32>,
    value_to_index: HashMap<i32, usize>,
}

impl List {
    fn new<I>(index_to_value: I) -> Self
    where
        I: Into<Vec<i32>>,
    {
        let index_to_value = index_to_value.into();
        let value_to_index = index_to_value
            .iter()
            .copied()
            .enumerate()
            .map(|(index, value)| (value, index))
            .collect();

        Self {
            index_to_value,
            value_to_index,
        }
    }

    fn get(&self, n: usize) -> Option<i32> {
        self.index_to_value.get(n).copied()
    }

    fn index_of(&self, i: i32) -> Option<usize> {
        self.value_to_index.get(&i).copied()
    }
}

fn main() {
    let list = List::new(vec![5, 2, 0, 4, 1, 3]);

    assert_eq!(list.get(2), Some(0));
    assert_eq!(list.get(3), Some(4));
    assert_eq!(list.index_of(0), Some(2));
    assert_eq!(list.index_of(4), Some(3));
}

Answer 2

This library提供了一个“IndexedTreeListSet”数据结构，实现了O(log n):

中需要的三个操作

查找索引 -> 元素
查找元素 -> 索引（又名索引）
在索引处插入元素

它像 Mo B. 一样，使用辅助哈希映射将元素映射到树中的节点，然后向上遍历到根。由于树中的每个节点都包含其相对索引，因此可以在根部计算绝对索引。

我从一种简单的方法（使用 O(n) 插入）切换到这种方法，并将插入的墙执行时间（每秒发生约 100 次）从约 100 毫秒减少到约 1 毫秒。

具有 O(log n) indexOf 操作的列表

List with O(log n) indexOf operation

indexing

vector

time-complexity

rust

data-structures