golang实现skiplist 跳表

2024-01-10 23:12
文章标签 实现 golang 跳表 skiplist

本文主要是介绍golang实现skiplist 跳表,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

跳表

package mainimport ("errors""math""math/rand"
)func main() {// 双向链表///**先理解查找过程Level 3: 1		 6Level 2: 1   3   6Level 1: 1 2 3 4 6比如 查找2 ; 从高层往下找;如果查找的值比当前值小 说明没有可查找的值2比1大 往当前层的下个节点查找,3层的后面没有了或者比后面的6小 ,往下层找2层 查找值比下个节点3还小 往下层找最后一层找到比如查找 4没有找到 3层往下到2层; 2层里 4比3大继续往前,比6小,往下层找从第一层的继续往前找比如查找 5第一层的3开始往前找到6比查找值5大,说明没有待查找值*//**插入流程找到插入的位置确定他当前的层数在他的层数连接当前节点如何确定层数?来一个概率的算法就行这样在数量大的时候能基本能达到2分查找的效果(概率是1/2)更新索引数组?我们在查找的时候的路径就可以拿来做插入的数据比如查找4找的路径是 3层的 1,2层的3 ;如果4是第三层的更新3层 1->4>6更新2层 1->3->4->6*//**删除流程 基本同上*//***/}// MAX_LEVEL 最高层数
const MAX_LEVEL = 16type T comparabletype skipListHandle[T comparable] interface {insert(data T, score int32) (err error)delete(data T, score int32) intfindNode(data T, score int32) (error, *skipListNode[T])
}type skipListNode[T comparable] struct {data T// 排序分数score int32//层高level int// 下个节点 同时也是索引forwards []*skipListNode[T]
}type skipList[T comparable] struct {head, tail *skipListNode[T]// 跳表高度level int// 跳表长度length int32
}func createSkipList[T comparable](data T) *skipList[T] {return &skipList[T]{level:  1,length: 0,head:   createNode[T](data, math.MinInt32, MAX_LEVEL),}
}func createNode[T comparable](data T, score int32, level int) *skipListNode[T] {return &skipListNode[T]{data:     data,score:    score,forwards: make([]*skipListNode[T], MAX_LEVEL, MAX_LEVEL),level:    level,}
}
func (list *skipList[T]) Insert(data T, score int32) error {currenNode := list.head// 找到插入的位置// 记录插入的路径 记录第一个比待查找的值小的位置path := [MAX_LEVEL]*skipListNode[T]{}for i := MAX_LEVEL - 1; i >= 0; i-- {for currenNode.forwards[i] != nil {// 如果插入的位置比当前数据小 直接跳出循环并且高度下降if currenNode.forwards[i].score > score {path[i] = currenNodebreak}// 插入位置比当前的大,在当前层继续往前找currenNode = currenNode.forwards[i]}// 如果currenNode.forwards[i] == nil 说明是最后一个值了 所以直接插入if currenNode.forwards[i] == nil {path[i] = currenNode}}// 随机算法求得最大层数level := 1for i := 1; i < MAX_LEVEL; i++ {if rand.Int31()%7 == 1 {level++}}newNode := createNode(data, score, level)// 原有节点连接for i := 0; i <= level-1; i++ {next := path[i].forwards[i]// path[i]拿到第一个插入值小的位置 forwards[i] 是指在当前层它指向的下个节点newNode.forwards[i] = nextpath[i].forwards[i] = newNode}// 更新levelif level > list.level {list.level = level}list.length++return errors.New("插入失败")
}func (list *skipList[T]) Delete(data T, score int32) int {currenNode := list.head// 找到插入的位置// 记录插入的路径 记录第一个比待查找的值小的位置path := [MAX_LEVEL]*skipListNode[T]{}for i := list.level - 1; i >= 0; i-- {path[i] = list.headfor currenNode.forwards[i] != nil {// 記錄刪除的位置if currenNode.forwards[i].score == score && currenNode.forwards[i].data == data {path[i] = currenNodebreak}// 插入位置比当前的大,在当前层继续往前找currenNode = currenNode.forwards[i]}}currenNode = path[0].forwards[0]for i := currenNode.level - 1; i >= 0; i-- {if path[i] == list.head && currenNode.forwards[i] == nil {list.level = i}if nil == path[i].forwards[i] {path[i].forwards[i] = nil} else {path[i].forwards[i] = path[i].forwards[i].forwards[i]}}list.length--return 0
}func (list skipList[T]) FindNode(v T, score int32) (err error, node *skipListNode[T]) {cur := list.headfor i := list.level - 1; i >= 0; i-- {for nil != cur.forwards[i] {if cur.forwards[i].score == score && cur.forwards[i].data == v {return nil, cur.forwards[i]} else if cur.forwards[i].score > score {break}cur = cur.forwards[i]}}return errors.New("请传入查找的值"), nil
}

测试


package mainimport ("testing"
)func Test_createNode(t *testing.T) {sl := createSkipList[int](0)sl.Insert(1, 95)t.Log(sl.head.forwards[0])t.Log(sl.head.forwards[0].forwards[0])t.Log(sl)t.Log("-----------------------------")sl.Insert(2, 88)t.Log(sl.head.forwards[0])t.Log(sl.head.forwards[0].forwards[0])t.Log(sl.head.forwards[0].forwards[0].forwards[0])t.Log(sl)t.Log("-----------------------------")sl.Insert(3, 100)t.Log(sl.head.forwards[0])t.Log(sl.head.forwards[0].forwards[0])t.Log(sl.head.forwards[0].forwards[0].forwards[0])t.Log(sl.head.forwards[0].forwards[0].forwards[0].forwards[0])t.Log(sl)t.Log("-----------------------------")t.Log(sl.FindNode(2, 88))t.Log("-----------------------------")sl.Delete(1, 95)t.Log(sl.head.forwards[0])t.Log(sl.head.forwards[0].forwards[0])t.Log(sl.head.forwards[0].forwards[0].forwards[0])t.Log(sl)t.Log("-----------------------------")
}

这篇关于golang实现skiplist 跳表的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/592387

相关文章

Python3脚本实现Excel与TXT的智能转换

《Python3脚本实现Excel与TXT的智能转换》在数据处理的日常工作中,我们经常需要将Excel中的结构化数据转换为其他格式,本文将使用Python3实现Excel与TXT的智能转换,需要的可以... 目录场景应用:为什么需要这种转换技术解析:代码实现详解核心代码展示改进点说明实战演练:从Excel到

如何使用CSS3实现波浪式图片墙

《如何使用CSS3实现波浪式图片墙》:本文主要介绍了如何使用CSS3的transform属性和动画技巧实现波浪式图片墙,通过设置图片的垂直偏移量,并使用动画使其周期性地改变位置,可以创建出动态且具有波浪效果的图片墙,同时,还强调了响应式设计的重要性,以确保图片墙在不同设备上都能良好显示,详细内容请阅读本文,希望能对你有所帮助...

C# string转unicode字符的实现

《C#string转unicode字符的实现》本文主要介绍了C#string转unicode字符的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随... 目录1. 获取字符串中每个字符的 Unicode 值示例代码:输出:2. 将 Unicode 值格式化

python安装whl包并解决依赖关系的实现

《python安装whl包并解决依赖关系的实现》本文主要介绍了python安装whl包并解决依赖关系的实现,文中通过图文示例介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面... 目录一、什么是whl文件?二、我们为什么需要使用whl文件来安装python库?三、我们应该去哪儿下

Python脚本实现图片文件批量命名

《Python脚本实现图片文件批量命名》这篇文章主要为大家详细介绍了一个用python第三方库pillow写的批量处理图片命名的脚本,文中的示例代码讲解详细,感兴趣的小伙伴可以了解下... 目录前言源码批量处理图片尺寸脚本源码GUI界面源码打包成.exe可执行文件前言本文介绍一个用python第三方库pi

Java中将异步调用转为同步的五种实现方法

《Java中将异步调用转为同步的五种实现方法》本文介绍了将异步调用转为同步阻塞模式的五种方法:wait/notify、ReentrantLock+Condition、Future、CountDownL... 目录异步与同步的核心区别方法一:使用wait/notify + synchronized代码示例关键

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

Nginx实现动态封禁IP的步骤指南

《Nginx实现动态封禁IP的步骤指南》在日常的生产环境中,网站可能会遭遇恶意请求、DDoS攻击或其他有害的访问行为,为了应对这些情况,动态封禁IP是一项十分重要的安全策略,本篇博客将介绍如何通过NG... 目录1、简述2、实现方式3、使用 fail2ban 动态封禁3.1 安装 fail2ban3.2 配

Java中实现订单超时自动取消功能(最新推荐)

《Java中实现订单超时自动取消功能(最新推荐)》本文介绍了Java中实现订单超时自动取消功能的几种方法,包括定时任务、JDK延迟队列、Redis过期监听、Redisson分布式延迟队列、Rocket... 目录1、定时任务2、JDK延迟队列 DelayQueue(1)定义实现Delayed接口的实体类 (

将java程序打包成可执行文件的实现方式

《将java程序打包成可执行文件的实现方式》本文介绍了将Java程序打包成可执行文件的三种方法:手动打包(将编译后的代码及JRE运行环境一起打包),使用第三方打包工具(如Launch4j)和JDK自带... 目录1.问题提出2.如何将Java程序打包成可执行文件2.1将编译后的代码及jre运行环境一起打包2