关于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节点有个两个重要的特点：

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

上面的查找门路,

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

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

查找5

查找8

查找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…

关于go:golang泛型实现skiplist

一、写在后面

二、一个根本的skiplist的样子

2.1 图示

2.2 代码展现

三、查找

3.1 图示

3.2 代码展现

四、新增

4.1 抛硬币函数

4.2 梳理多层插入节点逻辑

4.3 图示

4.4 代码展现

五、删除

5.1 图示

5.2 代码展现

六、压测

七、残缺代码

评论

发表回复取消回复

更多文章

DDN HPC 存储硬件架构设计深度分析

探秘IO500：从Lustre并行文件系统出发，开启HPC存储性能新征程

苹果iOS打包的ipa应用无法安装？一篇文章带你了解可能的原因及排查方法

图解Golang：从零开始实现简易版过期LRU缓存

关于go:golang泛型实现skiplist

一、写在后面

二、 一个根本的skiplist的样子

2.1 图示

2.2 代码展现

三、查找

3.1 图示

3.2 代码展现

四、新增

4.1 抛硬币函数

4.2 梳理多层插入节点逻辑

4.3 图示

4.4 代码展现

五、删除

5.1 图示

5.2 代码展现

六、压测

七、残缺代码

评论

发表回复 取消回复

更多文章

DDN HPC 存储硬件架构设计深度分析

探秘IO500：从Lustre并行文件系统出发，开启HPC存储性能新征程

苹果iOS打包的ipa应用无法安装？一篇文章带你了解可能的原因及排查方法

图解Golang：从零开始实现简易版过期LRU缓存

二、一个根本的skiplist的样子

发表回复取消回复