关于go:golang泛型实现skiplist

一、写在后面

skiplist 是一种有序的数据结构, 不同于各种均衡树, skiplist 看起来就是多层的链表, 具体点每个元素是个数组, 这个元素的数组除了 0 层是和下个元素直连, 1 层和 n 层之间可能和下个, 或者下下个节点连接起来。

这些 skiplist 节点的多层构造，形成施行二分搜寻的根底, 实践从而达到可观的效率, 开源界赫赫有名的 redis 的 zset 一部分应用 skiplist。

对于这个被吹爆了的数据，上面会应用 redis 的套路在 go 外面实现下, 是骡子是马拉进去溜溜压测下性能如何。

二、一个根本的 skiplist 的样子

2.1 图示

2.2 代码展现

表头和节点

type Node[T any] struct {
    score float64
    elem  T
    // 后退指针
    backward  *Node[T]
    NodeLevel []struct {
        // 指向后退节点, 是指向 tail 的方向
        forward *Node[T]
        span    int
    }
}

type SkipList[T any] struct {head *Node[T]
    tail *Node[T]

    r      *rand.Rand
    length int
    level  int
}

三、查找

3.1 图示

还是以下面的 skiplist 为例, 上面会画出查找每个元素的搜寻门路。

skiplist 外面 head 节点有个两个重要的特点：

1. head 节点的层数等于最大节点和层数, 个别实现中会有 MaxLevel 记录最大结点层数
2. head 节点是与数据节点之间有链接关系的

上面的查找门路,

• 实线示意查找的门路,
• 虚线示意节点间的关系

查找的过程就是先从 head 节点的 MaxLevel-1 索引查找, 查找的大抵走位是向右向下向右向下 … 就迫近指标地位

1. 查找 5

2. 查找 8

3. 查找 10

3.2 代码展现

// 获取
func (s *SkipList[T]) GetWithErr(score float64) (elem T, err error) {

    x := s.head
    for i := s.level - 1; i >= 0; i-- {for x.NodeLevel[i].forward != nil && (x.NodeLevel[i].forward.score < score) {x = x.NodeLevel[i].forward
        }

    }

    x = x.NodeLevel[0].forward
    if x != nil && score == x.score {return x.elem, nil}

    err = ErrNotFound
    return
}

四、新增

新增先应用 update[] 数组保护每层须要插入节点的地位, 通过抛硬币的函数决定这个新节点的 level, 最初批改节点的前后关系, 就是插入链表节点的多层版本, 保护多层信息就是 update[] 干的事件。

4.1 抛硬币函数

把 1 当成硬币的侧面, 0 当作硬币的背面, 直到抛到 0 时就完结, 这时间断的侧面就是 skiplist 外面须要建的 level 数。

func (s *SkipList[T]) rand() int {
    level := 1
    for {if s.r.Int()%2 == 0 {break}
        level++
    }

    if level < SKIPLIST_MAXLEVEL {return level}

    return SKIPLIST_MAXLEVEL
}

4.2 梳理多层插入节点逻辑

如果在单链表中执行插入操作

• prev是待插入节点的后面一个节点,
• 待插入节点是new, new.next = prev.next， prev.next = new, 即可实现一个节点的插入。

skiplist 的插入和单链表类似, 无非是扩大到多层, 应用一个数组记录每一层的 prev 指针，skiplist 的新节点也是数组，这里应用一个 for 循环遍历层，每个层内的操作与单链表中的操作是一样的。

4.3 图示

插入节点 5

4.4 代码展现

func (s *SkipList[T]) InsertInner(score float64, elem T, level int) *SkipList[T] {
    var (update [SKIPLIST_MAXLEVEL]*Node[T]
        rank   [SKIPLIST_MAXLEVEL]int
    )

    x := s.head
    var x2 *Node[T]
    for i := s.level - 1; i >= 0; i-- {
        if i == s.level-1 {rank[i] = 0
        } else {rank[i] = rank[i+1]
        }

        for x.NodeLevel[i].forward != nil &&
            (x.NodeLevel[i].forward.score < score) {
            // 临时不反对反复的 key, 前面再说 TODO
            //|| x.NodeLevel[i].forward.score == score &&
            //s.compare(elem, x.NodeLevel[i].forward.elem) < 0) {

            //TODO span 的含意是?
            rank[i] += x.NodeLevel[i].span
            x = x.NodeLevel[i].forward
        }

        // 保留插入地位的前一个节点, 保留的数量就是 level 的值
        update[i] = x
    }

    // 这个 score 曾经存在间接返回
    x2 = x.NodeLevel[0].forward
    if x2 != nil && score == x2.score {
        x2.elem = elem
        return s
    }

    if level > s.level {
        // 这次新的 level 与老的 level 的差值, 给填充 head 指针
        for i := s.level; i < level; i++ {
            // TODO rank 的含意
            rank[i] = 0
            update[i] = s.head
            update[i].NodeLevel[i].span = s.length
        }
        s.level = level
    }

    // 创立新节点
    x = newNode(level, score, elem)
    for i := 0; i < level; i++ {// x.NodeLevel[i]的节点假如等于 a, 须要插入的节点 x 在 a 之后,
        // a, x, a.forward 三者的关系就是[a, x, a.forward]
        // 那就变成了 x.forward = a.forward, 批改 x.forward 的指向
        // a.forward = x
        // 看如下两行代码
        x.NodeLevel[i].forward = update[i].NodeLevel[i].forward
        update[i].NodeLevel[i].forward = x

        x.NodeLevel[i].span = update[i].NodeLevel[i].span - (rank[0] - rank[i])
        update[i].NodeLevel[i].span = rank[0] - rank[i] + 1
    }

    for i := level; i < s.level; i++ {update[i].NodeLevel[i].span++
    }

    if update[0] != s.head {x.backward = update[0]
    }

    if x.NodeLevel[0].forward != nil {x.NodeLevel[0].forward.backward = x
    } else {s.tail = x}

    s.length++
    return s
}

五、删除

如果在单链表中执行删除操作, prev 是待删除节点的后面一个节点, 如果要删除待删除节点 n, 间接 prev.next = n.next 就实现一个节点的删除, skiplist 的删除也和单链表相似。

5.1 图示

删除节点 5

5.2 代码展现

func (s *SkipList[T]) removeNode(x *Node[T], update []*Node[T]) {
    for i := 0; i < s.level; i++ {if update[i].NodeLevel[i].forward == x {update[i].NodeLevel[i].span += x.NodeLevel[i].span - 1
            update[i].NodeLevel[i].forward = x.NodeLevel[i].forward
        } else {update[i].NodeLevel[i].span -= 1
        }
    }

    if x.NodeLevel[0].forward != nil {
        // 原来左边节点 backward 指针间接指各右边节点, 当初指向左左节点
        x.NodeLevel[0].forward.backward = x.backward
    } else {
        // 最初一个元素, 批改下尾指针的地位
        s.tail = x.backward
    }

    for s.level > 1 && s.head.NodeLevel[s.level-1].forward == nil {s.level--}
    s.length--
}

// 依据 score 删除元素
func (s *SkipList[T]) Remove(score float64) *SkipList[T] {var update [SKIPLIST_MAXLEVEL]*Node[T]
    x := s.head
    for i := s.level - 1; i >= 0; i-- {for x.NodeLevel[i].forward != nil && (x.NodeLevel[i].forward.score < score) {x = x.NodeLevel[i].forward
        }
        update[i] = x
    }

    x = x.NodeLevel[0].forward
    if x != nil && score == x.score {s.removeNode(x, update[:])
        return s
    }

    return s
}

六、压测

从压测上来看, 本文中的 skiplist 的实现, 相比 golang map 性能靠近，同时放弃有序个性，值得王婆卖瓜 …

goos: darwin
goarch: amd64
pkg: github.com/guonaihong/gstl/skiplist
cpu: Intel(R) Core(TM) i7-1068NG7 CPU @ 2.30GHz
BenchmarkGet-8          1000000000             0.7746 ns/op
BenchmarkGetStd-8       1000000000             0.7847 ns/op
PASS
ok      github.com/guonaihong/gstl/skiplist    178.377s

七、残缺代码

有小伙伴对残缺实现感兴趣的可查看如下链接, 除了下面聊过的 Get、Set、Remove 外, 还有遍历、TopMax、TopMin 等操作。

https://github.com/guonaihong…