方便的跳表

一个性能优良且方便的跳表，具有高级范围查询和 serde 支持。

要将此添加到您的项目中，只需将以下内容添加到您的 Cargo.toml 中

convenient-skiplist = "1.0.3"

或者，如果您想要 serde 支持

convenient-skiplist = { "version" = "1.0.3", features = ["serde_support"] }

简单示例

use convenient_skiplist::SkipList;

fn main() {
    // Make a new skiplist
    let mut sk = SkipList::new();
    for i in 0..5u32 {
        // Inserts are O(log(n)) on average
        sk.insert(i);
    }
    // You can print the skiplist!
    dbg!(&sk);
    // You can check if the skiplist contains an element, O(log(n))
    assert!(sk.contains(&0));
    assert!(!sk.contains(&10));
    assert!(sk.remove(&0)); // remove is also O(log(n))
}

这将输出

[src/main.rs:11] &sk = SkipList(wall_height: 4), and table:
NegInf -> PosInf
NegInf -> Value(2) -> PosInf
NegInf -> Value(1) -> Value(2) -> PosInf
NegInf -> Value(0) -> Value(1) -> Value(2) -> Value(3) -> Value(4) -> PosInf

向下滚动或查看 examples 文件夹以获取更多信息。

本库提供的内容

本库提供了构建和遍历跳表的工具。底层使用指针和内联比较函数。在调试模式下，有一些不变性检查，但在发布模式下为了性能原因被禁用。

基本功能

您可以构建一个跳表，并在跳表中插入元素并检查它们是否存在（使用 contains）；

// Create a new skiplist
let mut sk = SkipList::new();

// Insert an element
sk.insert(0u32);

// Verify that the element exists in the SkipList
assert!(sk.contains(&0))

// Remove an element from the skiplist:
assert!(sk.remove(&0))

// Check the length
assert_eq!(sk.len(), 0)
assert_eq!(sk.is_empty(), true)

// Find the index of an element
sk.insert(1u32);
sk.insert(2u32);
sk.insert(3u32);

assert_eq!(sk.index_of(&1), Some(0))
assert_eq!(sk.index_of(&2), Some(1))
assert_eq!(sk.index_of(&99), None)

索引

方便的跳表具有几个基于索引的功能

use convenient_skiplist::SkipList;

let mut sk = SkipList::from((b'a'..=b'z').map(|c| c as char));

// Find the index (rank) of an item
assert_eq!(sk.index_of(&'a'), Some(0));
assert_eq!(sk.index_of(&'b'), Some(1));
assert_eq!(sk.index_of(&'z'), Some(25));
assert_eq!(sk.index_of(&'💩'), None);

// Get the element at index (rank -> value)
assert_eq!(sk.at_index(0), Some(&'a'));
assert_eq!(sk.at_index(25), Some(&'z'));
assert_eq!(sk.at_index(100), None);

// We can also efficiently pop maximum and minimum values:
assert_eq!(vec!['z'], sk.pop_max(1));
assert_eq!(vec!['a', 'b', 'c'], sk.pop_min(3));

迭代器

目前有三种主要方法可以遍历跳表

use convenient_skiplist::SkipList;

// First make a skiplist with plenty of elements:

let sk = SkipList::new();
for i in 0..500u32 {
    sk.insert(i);
}

// SkipList::iter_all -- Iterator over all elements (slow!)

for i in sk.iter_all() {
     println!("{}", i);
}

// SkipList::range -- Fast, typically bounded by range width.

for i in sk.range(&200, &400) {
     println!("{}", i);
}

// SkipList::range_with -- Fast, typically bounded by range width.
// You need to provide a comparison function to guide the
// iterator towards the desired range.

use convenient_skiplist::iter::RangeHint;

let my_range_fn = |&ele| {
    if ele < 111 {
        RangeHint::SmallerThanRange
    } else if ele > 333 {
        RangeHint::LargerThanRange
    } else {
        RangeHint::InRange
    }
};

for i in sk.range_with(my_range_fn) {
     println!("{}", i);
}

性能

一般规则：突变操作是微秒级，不可变操作是纳秒级。主要的突变瓶颈是堆分配和释放。

您可以使用 cargo bench 来测试 convenient-skiplist 对您性能的影响

$ cargo bench

时间/空间复杂度

• 跳表的空间复杂度为 ~2n。
• SkipList::insert - O(logn) 时间 | ~O(1) 空间
• Skiplist::contains - O(logn) 时间
• Skiplist::remove - O(logn) 时间
• Skiplist::iter_all - O(n) 时间 | O(1) 空间（迭代器每次只产生一个元素）
• Skiplist::range - O(logn + k)，其中 k 是范围宽度 | O(1) 空间（迭代器每次只产生一个元素）
• Skiplist::range_with - O(logn + k + flogn)，其中k为范围宽度，f为传递函数的成本 | O(1) 空间（迭代器每次只产生一个元素）
• Skiplist::index_of - O(logn) 时间
• Skiplist::at_index - O(logn) 时间
• Skiplist::pop_min - O(logn * k) 时间 | O(k) 空间，其中k为要弹出元素的数量
• Skiplist::at_index - O(logn * k) 时间 | O(logn + k) 空间，其中k为要弹出元素的数量
• PartialEq<SkipList> - O(n) 时间；比较两个跳表是否包含相同的元素
• From<FromIterator<T>> - O(nlogn) 时间；从包含n个元素的迭代器生成跳表
• Skiplist::pop_back - O(log n) 时间
• Skiplist::pop_front - O(1) 时间

数据结构描述

跳表是有序元素的概率性数据结构。它类似于二维链表，其中最底下一行就是一个普通的链表。

每一行结构为 "负无穷大" -> ... 有序链表 ... -> "正无穷大"。每个元素都生活在随机高度的塔中（几何分布），并且你只能向下移动塔。你还可以像普通链表一样向右移动。

数据结构背后的主要思想是，你从左上角开始，如果你当前搜索的元素大于你右侧的元素，你就可以跳过。这让你可以避免大量的工作，实际上跳过了你本来要搜索的元素。否则，你向下移动一个层次，并再次尝试跳过。重复此过程，直到你到达底部，在那里你可以像普通链表一样向右移动。

跳表的示例

更高级的示例

use convenient_skiplist::{RangeHint, SkipList};
use std::cmp::Ordering;

#[derive(PartialEq, Debug, Clone)]
struct MoreComplex {
    pub score: f64,
    pub data: String,
}

// We're going to sort the skiplist by the "score" field
impl PartialOrd for MoreComplex {
    fn partial_cmp(&self, other: &MoreComplex) -> Option<Ordering> {
        self.score.partial_cmp(&other.score)
    }
}

fn main() {
    let mut sk = SkipList::new();
    for i in 0..100 {
        sk.insert(MoreComplex {
            score: i as f64 / 100.0,
            data: i.to_string(),
        });
    }
    let range = sk.range_with(|ele| {
        if ele.score <= 0.05 {
            RangeHint::SmallerThanRange
        } else if ele.score <= 0.55 {
            RangeHint::InRange
        } else {
            RangeHint::LargerThanRange
        }
    });
    for item in range {
        println!("{:?}", item);
    }
}

正确性

此库使用了很多不安全的。它更接近cpp库，只是恰好是用rust实现的。特别是，我不会过分强调迭代器。我使用迭代器做一些有趣的事情，以使生命周期正常工作。

但是 miri 似乎喜欢它，所以 🤷