Golang中怎么使用跳表實現SortedSet

本篇內容介紹了“Golang中怎么使用跳表實現SortedSet”的有關知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠學有所成！

結構定義

實現ZRange命令最簡單的數據結構是有序鏈表:

在有序鏈表上實現ZRange key start end命令需要進行end次查詢, 即時間復雜度為 O(n)

跳表的優化思路是添加上層鏈表，上層鏈表中會跳過一些節點。如圖所示:

在有兩層的跳表中，搜索的時間復雜度降低為了O(n / 2)。以此類推在有 log2(n) 層的跳表中，搜索元素的時間復雜度為O(log n)。

了解數據結構之后，可以定義相關的類型了:

// 對外的元素抽象type Element struct {
    Member string
    Score  float64}type Node struct {
    Element // 元素的名稱和 score
    backward *Node // 后向指針
    level []*Level // 前向指針, level[0] 為最下層}// 節點中每一層的抽象 type Level struct {
    forward *Node // 指向同層中的下一個節點
    span int64 // 到 forward 跳過的節點數}// 跳表的定義type skiplist struct {
    header *Node
    tail *Node
    length int64
    level int16}

用一張圖來表示一下:

查找節點

有了上文的描述查找節點的邏輯不難實現, 以 RangeByRank 的核心邏輯為例:

// 尋找排名為 rank 的節點, rank 從1開始func (skiplist *skiplist) getByRank(rank int64)*Node {    var i int64 = 0
    n := skiplist.header    // 從頂層向下查詢
    for level := skiplist.level - 1; level >= 0; level-- {        // 從當前層向前搜索
        // 若當前層的下一個節點已經超過目標 (i+n.level[level].span > rank)，則結束當前層搜索進入下一層
        for n.level[level].forward != nil && (i+n.level[level].span) <= rank {
            i += n.level[level].span
            n = n.level[level].forward
        }        if i == rank {            return n
        }
    }    return nil}

ZRangeByScore 命令需要 getFirstInScoreRange 函數找到分數范圍內第一個節點:

func (skiplist *skiplist) getFirstInScoreRange(min *ScoreBorder, max *ScoreBorder) *Node {    // 判斷跳表和范圍是否有交集，若無交集提早返回
    if !skiplist.hasInRange(min, max) {        return nil
    }
    n := skiplist.header    // 從頂層向下查詢
    for level := skiplist.level - 1; level >= 0; level-- {        // 若 forward 節點仍未進入范圍則繼續向前(forward)
        // 若 forward 節點已進入范圍，當 level > 0 時 forward 節點不能保證是 *第一個* 在 min 范圍內的節點， 因此需進入下一層查找
        for n.level[level].forward != nil && !min.less(n.level[level].forward.Score) {
            n = n.level[level].forward
        }
    }    // 當從外層循環退出時 level=0 (最下層), n.level[0].forward 一定是 min 范圍內的第一個節點
    n = n.level[0].forward    if !max.greater(n.Score) {        return nil
    }    return n
}

插入節點

插入節點的操作比較多，我們以注釋的方式進行說明:

func (skiplist *skiplist)insert(member string, score float64)*Node {    // 尋找新節點的先驅節點，它們的 forward 將指向新節點
    // 因為每層都有一個 forward 指針, 所以每層都會對應一個先驅節點
    // 找到這些先驅節點并保存在 update 數組中
    update := make([]*Node, maxLevel)
    rank := make([]int64, maxLevel) // 保存各層先驅節點的排名，用于計算span
    node := skiplist.header    for i := skiplist.level - 1; i >= 0; i-- { // 從上層向下尋找
        // 初始化 rank
        if i == skiplist.level - 1 {
            rank[i] = 0
        } else {
            rank[i] = rank[i + 1]
        }        if node.level[i] != nil {            // 遍歷搜索
            for node.level[i].forward != nil &&
                (node.level[i].forward.Score < score ||
                    (node.level[i].forward.Score == score && node.level[i].forward.Member < member)) { // same score, different key
                rank[i] += node.level[i].span
                node = node.level[i].forward
            }
        }
        update[i] = node
    }
    level := randomLevel() // 隨機決定新節點的層數
    // 可能需要創建新的層
    if level > skiplist.level {        for i := skiplist.level; i < level; i++ {
            rank[i] = 0
            update[i] = skiplist.header
            update[i].level[i].span = skiplist.length
        }
        skiplist.level = level
    }    // 創建新節點并插入跳表
    node = makeNode(level, score, member)    for i := int16(0); i < level; i++ {        // 新節點的 forward 指向先驅節點的 forward
        node.level[i].forward = update[i].level[i].forward        // 先驅節點的 forward 指向新節點
        update[i].level[i].forward = node        // 計算先驅節點和新節點的 span
        node.level[i].span = update[i].level[i].span - (rank[0] - rank[i])
        update[i].level[i].span = (rank[0] - rank[i]) + 1
    }    // 新節點可能不會包含所有層
    // 對于沒有層，先驅節點的 span 會加1 (后面插入了新節點導致span+1)
    for i := level; i < skiplist.level; i++ {
        update[i].level[i].span++
    }    // 更新后向指針
    if update[0] == skiplist.header {
        node.backward = nil
    } else {
        node.backward = update[0]
    }    if node.level[0].forward != nil {
        node.level[0].forward.backward = node
    } else {
        skiplist.tail = node
    }
    skiplist.length++    return node
}

randomLevel 用于隨機決定新節點包含的層數，隨機結果出現2的概率是出現1的25%， 出現3的概率是出現2的25%:

func randomLevel() int16 {
    level := int16(1)    for float32(rand.Int31()&0xFFFF) < (0.25 * 0xFFFF) {
        level++
    }    if level < maxLevel {        return level
    }    return maxLevel
}

刪除節點

刪除節點的思路與插入節點基本一致:

// 刪除操作可能一次刪除多個節點func (skiplist *skiplist) RemoveRangeByRank(start int64, stop int64)(removed []*Element) {    var i int64 = 0  // 當前指針的排名
    update := make([]*Node, maxLevel)
    removed = make([]*Element, 0)    // 從頂層向下尋找目標的先驅節點
    node := skiplist.header    for level := skiplist.level - 1; level >= 0; level-- {        for node.level[level].forward != nil && (i+node.level[level].span) < start {
            i += node.level[level].span
            node = node.level[level].forward
        }
        update[level] = node
    }
    i++
    node = node.level[0].forward // node 是目標范圍內第一個節點
    // 刪除范圍內的所有節點
    for node != nil && i < stop {
        next := node.level[0].forward
        removedElement := node.Element
        removed = append(removed, &removedElement)
        skiplist.removeNode(node, update)
        node = next
        i++
    }    return removed
}

接下來分析一下執行具體節點刪除操作的removeNode函數:

// 傳入目標節點和刪除后的先驅節點// 在批量刪除時我們傳入的 update 數組是相同的func (skiplist *skiplist) removeNode(node *Node, update []*Node) {    for i := int16(0); i < skiplist.level; i++ {        // 如果先驅節點的forward指針指向了目標節點，則需要修改先驅的forward指針跳過要刪除的目標節點
        // 同時更新先驅的 span
        if update[i].level[i].forward == node {
            update[i].level[i].span += node.level[i].span - 1
            update[i].level[i].forward = node.level[i].forward
        } else {
            update[i].level[i].span--
        }
    }    // 修改目標節點后繼節點的backward指針
    if node.level[0].forward != nil {
        node.level[0].forward.backward = node.backward
    } else {
        skiplist.tail = node.backward
    }    // 必要時刪除空白的層
    for skiplist.level > 1 && skiplist.header.level[skiplist.level-1].forward == nil {
        skiplist.level--
    }
    skiplist.length--
}

“Golang中怎么使用跳表實現SortedSet”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識可以關注億速云網站，小編將為大家輸出更多高質量的實用文章！