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

相关文章

SpringBoot3实现Gzip压缩优化的技术指南

《SpringBoot3实现Gzip压缩优化的技术指南》随着Web应用的用户量和数据量增加,网络带宽和页面加载速度逐渐成为瓶颈,为了减少数据传输量,提高用户体验,我们可以使用Gzip压缩HTTP响应,... 目录1、简述2、配置2.1 添加依赖2.2 配置 Gzip 压缩3、服务端应用4、前端应用4.1 N

SpringBoot实现数据库读写分离的3种方法小结

《SpringBoot实现数据库读写分离的3种方法小结》为了提高系统的读写性能和可用性,读写分离是一种经典的数据库架构模式,在SpringBoot应用中,有多种方式可以实现数据库读写分离,本文将介绍三... 目录一、数据库读写分离概述二、方案一:基于AbstractRoutingDataSource实现动态

Python FastAPI+Celery+RabbitMQ实现分布式图片水印处理系统

《PythonFastAPI+Celery+RabbitMQ实现分布式图片水印处理系统》这篇文章主要为大家详细介绍了PythonFastAPI如何结合Celery以及RabbitMQ实现简单的分布式... 实现思路FastAPI 服务器Celery 任务队列RabbitMQ 作为消息代理定时任务处理完整

Java枚举类实现Key-Value映射的多种实现方式

《Java枚举类实现Key-Value映射的多种实现方式》在Java开发中,枚举(Enum)是一种特殊的类,本文将详细介绍Java枚举类实现key-value映射的多种方式,有需要的小伙伴可以根据需要... 目录前言一、基础实现方式1.1 为枚举添加属性和构造方法二、http://www.cppcns.co

使用Python实现快速搭建本地HTTP服务器

《使用Python实现快速搭建本地HTTP服务器》:本文主要介绍如何使用Python快速搭建本地HTTP服务器,轻松实现一键HTTP文件共享,同时结合二维码技术,让访问更简单,感兴趣的小伙伴可以了... 目录1. 概述2. 快速搭建 HTTP 文件共享服务2.1 核心思路2.2 代码实现2.3 代码解读3.

MySQL双主搭建+keepalived高可用的实现

《MySQL双主搭建+keepalived高可用的实现》本文主要介绍了MySQL双主搭建+keepalived高可用的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,... 目录一、测试环境准备二、主从搭建1.创建复制用户2.创建复制关系3.开启复制,确认复制是否成功4.同

Java实现文件图片的预览和下载功能

《Java实现文件图片的预览和下载功能》这篇文章主要为大家详细介绍了如何使用Java实现文件图片的预览和下载功能,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... Java实现文件(图片)的预览和下载 @ApiOperation("访问文件") @GetMapping("

使用Sentinel自定义返回和实现区分来源方式

《使用Sentinel自定义返回和实现区分来源方式》:本文主要介绍使用Sentinel自定义返回和实现区分来源方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Sentinel自定义返回和实现区分来源1. 自定义错误返回2. 实现区分来源总结Sentinel自定

Java实现时间与字符串互相转换详解

《Java实现时间与字符串互相转换详解》这篇文章主要为大家详细介绍了Java中实现时间与字符串互相转换的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、日期格式化为字符串(一)使用预定义格式(二)自定义格式二、字符串解析为日期(一)解析ISO格式字符串(二)解析自定义

opencv图像处理之指纹验证的实现

《opencv图像处理之指纹验证的实现》本文主要介绍了opencv图像处理之指纹验证的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学... 目录一、简介二、具体案例实现1. 图像显示函数2. 指纹验证函数3. 主函数4、运行结果三、总结一、