Rust 跳錶

前面幾個章節我們講過了鏈表，可以發現它有一個特點，查找某個元素時，我們需要迭代進行查詢，如果鏈表長度很小，那麼查詢也是很快的，如果鏈表很大，那麼查詢就得靠運氣了，查找的節點在鏈表的前部，還是很快，在鏈表的尾部，那麼就幾乎迭代整個鏈表了。爲了改進查找的效率，及不依賴運氣，計算機先驅們，設計了跳錶算法，跳錶的核心就是能夠跳過一些節點查找，😄。

在實際實現中，我們按照下面圖示進行實現，

它有一個前提，就是節點需要排序。

我們先看佈局

use std::{cell::RefCell, rc::Rc};
type Link = Option<Rc<RefCell<Node>>>;
struct Node {
    next: Vec<Link>,
    pub value: u64,
}
impl Node {
    fn new(next: Vec<Link>, value: u64) -> Rc<RefCell<Node>> {
        Rc::new(RefCell::new(Node { next, value }))
    }
}
pub(crate) struct SkipList {
    head: Link,
    tails: Vec<Link>,
    max_level: usize,
    pub length: u64,
}

我們實現新增，查找。新增的關鍵點是循環每個層，當每個層的尾部節點有值時，將它的下一個節點指向這個新節點，然後再將尾部節點指向這個節點。

tail-->old node  ，old node --> new node  ,tail --> new node

impl SkipList {
   pub  fn new(level: usize) -> Self {
        Self {
            head: None,
            tails: vec![None; level],
            max_level: level-1, // 需要，否則報溢出
            length: 0,
        }
    }
// 隨機拋硬幣，獲得層數
    fn get_level(&self) -> usize {
        let mut n = 0;
        while rand::random::<bool>() && n < self.max_level {
            n += 1;
        }
        n
    }
// 添加，第一個節點，有最大層數
    pub fn append(&mut self, value: u64) {
        let level = 1+if self.head.is_none() {
            self.max_level-1
        } else {
            self.get_level()
        };
// 創建新的節點
        let new = Node::new(vec![None; level], value);
        for i in 0..level {
            if let Some(old) = self.tails[i].take() {
                let next = &mut old.borrow_mut().next;
                next[i] = Some(new.clone());
            }
            self.tails[i] = Some(new.clone());
        }
        if self.head.is_none() {
            self.head = Some(new.clone());
        }
        self.length += 1;
    }
// 查找
    pub fn find(&self, value: u64) -> Option<u64> {
        match self.head {
            Some(ref head) => {
            // 先從最大層，最高層查找
                let mut start_level = self.max_level;
                let node = head.clone();
                let mut result = None;
                // 獲取到某層有節點，退出取出層數。
                loop {
                    if node.borrow().next[start_level].is_some() {
                        break;
                    }
                    start_level -= 1;
                }
// 得到這個節點
                let mut n = node;
// 從這個高層開始迭代
                for level in (0..=start_level).rev() {
                // 找到它的值，如果獲取的值大於要找的值，
                // 它退出循環，可以得到當前的節點
                // 否則，獲取它額下一個節點繼續比較
                    loop {
                        let next = n.clone();
                        match next.borrow().next[level] {
                            Some(ref next) if next.borrow().value <= value => n = next.clone(),
                            _ => break
                        };
                    }
                    // 確認當前的節點值是否相同
                    if n.borrow().value == value {
                        let tmp = n.borrow();
                        result = Some(tmp.value);
                        break;
                    }
                }
                result
            }
            None => None,
        }
    }
}

我們測試

fn main(){
    let now = Instant::now();
    let mut list = skip_list::SkipList::new(10); 
    // 從小到大的排序
    for i in 1..1000{
        list.append(i);
    }
   let result= list.find(200);
   match result {
    Some(_) => println!("find"),
    None => println!("not found"),
}
    println!("the cost is {:?}",now.elapsed());
}

刪除節點我沒有實現，還有一些其他的功能，歡迎你來實現。

你有好的想法和建議，歡迎留言！

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/msm_7Fg9KGFICSgSOQCPVQ