[C++][数据结构][跳表]详细讲解
目录
- 0.什么是跳表?
- 1.SkipList的优化思路
- 2.SkipList的效率如何保证?
- 3.SkipList实现
- 4.SkipList VS 平衡搜索树 && Hash
0.什么是跳表?
- SkipList本质上也是一种查找结构,用于解决算法中的查找问题,跟平衡搜索树和哈希表的价值是一样的,可以作为key或者key/value的查找模型
- SkipList,是在有序链表的基础上发展起来的
- 如果是一个有序的链表,查找数据的时间复杂度是 O ( N ) O(N) O(N)
1.SkipList的优化思路
-
假如每相邻两个节点升高一层,增加一个指针,让指针指向下下个节点,如下图b所示
- 这样所有新增加的指针连成了一个新的链表,但它包含的节点个数只有原来的一半
- 由于新增加的指针,我们不再需要与链表中每个节点逐个进行比较了,需要比较的节点数大概只有原来的一半
-
以此类推,可以在第二层新产生的链表上,继续为每相邻的两个节点升高一层,增加一个指针,从而产生第三层链表,这样搜索效率就进一步提高了,如下图c
-
SkipList正是受这种多层链表的想法的启发而设计出来的
-
实际上,按照上面生成链表的方式,上面每一层链表的节点个数,是下面一层的节点个数的一半,这样查找过程就非常类似二分查找,使得查找的时间复杂度可以降低到 O ( l o g 2 N ) O(log_2N) O(log2N)
-
但是这个结构在插入删除数据的时候有很大的问题
-
插入或者删除一个节点之后,就会打乱上下相邻两层链表上节点个数严格的2:1的对应关系
-
如果要维持这种对应关系,就必须把新插入的节点后面的所有节点(也包括新插入的节点)重新进行调整,这会让时间复杂度重新蜕化成O(n)
-
-
SkipList的设计为了避免这种问题,做了一个大胆的处理
-
不再严格要求对应比例关系,而是插入一个节点的时候随机出一个层数
-
这样每次插入和删除都不需要考虑其他节点的层数, 这样就好处理多了
-
2.SkipList的效率如何保证?
-
SkipList插入一个节点时随机出一个层数,听起来这么随意,如何保证搜索时的效率呢?
-
首先要细节分析的是这个随机层数是怎么来的
- 一般跳表会设计一个最大层数maxLevel的限制
- 其次会设置一个多增加一层的概率p
- 计算这个随机层数的伪代码如下图:
-
**参考:**在Redis的SkipList实现中,这两个参数的取值为:
p = 1/4; maxLevel = 32;
-
根据前面
randomLevel()
的伪代码,产生越高的节点层数,概率越低- 节点层数至少为1,而大于1的节点层数,满足一个概率分布
- 节点层数恰好等于1的概率为 1 − p 1-p 1−p
- 节点层数大于等于2的概率为 p p p,而节点层数恰好等于2的概率为 p ∗ ( 1 − p ) p*(1-p) p∗(1−p)
- 节点层数大于等于3的概率为 p 2 p^2 p2,而节点层数恰好等于3的概率为 p 2 ∗ ( 1 − p ) p^2*(1-p) p2∗(1−p)
- 节点层数大于等于4的概率为 p 3 p^3 p3,而节点层数恰好等于4的概率为 p 3 ∗ ( 1 − p ) p^3*(1-p) p3∗(1−p)
-
因此,一个节点的平均层数(即包含的平均指针数目),计算如下:
- 当 p = 1 / 2 p=1/2 p=1/2时,每个节点所包含的平均指针数目为2
- 当 p = 1 / 4 p=1/4 p=1/4时,每个节点所包含的平均指针数目为1.33
-
SkipList的平均时间复杂度为: O ( l o g N ) O(logN) O(logN),
3.SkipList实现
- 插入结点的关键是找到这个位置的每一层前一个结点
- 比它小,向下走
- 比它大,向右走
struct SkipListNode
{int _val;vector<SkipListNode*> _nextV;SkipListNode(int val, int level): _val(val), _nextV(level, nullptr){}
};class Skiplist
{typedef SkipListNode Node;
public:Skiplist(){srand(time(nullptr));_head = new Node(-1, 1); // 头节点,层数是1}bool Search(int target){Node* cur = _head;int level = _head->_nextV.size() - 1;while (level >= 0){if (cur->_nextV[level] && target > cur->_nextV[level]->_val){// 目标值比下一个结点值大,向右走cur = cur->_nextV[level];}else if (!cur->_nextV[level] || target < cur->_nextV[level]->_val){// 下一个结点是空(尾) || 目标值比下一个节点值要小,向下走level--;}else{return true;}}return false;}void Add(int num){vector<Node*> preV = FindPrevNode(num);int n = RandomLevel();Node* newnode = new Node(num, n);// 如果n超过当前最大的层数,那就升高一下_head的层数if (n > _head->_nextV.size()){_head->_nextV.resize(n, nullptr);preV.resize(n, _head);}// 链接前后结点for (size_t i = 0; i < n; i++){newnode->_nextV[i] = preV[i]->_nextV[i];preV[i]->_nextV[i] = newnode;}}bool Erase(int num){vector<Node*> preV = FindPrevNode(num);// 第一层下一个不是val,则val不在表中if (!preV[0]->_nextV[0] || preV[0]->_nextV[0]->_val != num){return false;}Node* del = preV[0]->_nextV[0];// del结点每一层前后指针链接起来for (size_t i = 0; i < del->_nextV.size(); i++){preV[i]->_nextV[i] = del->_nextV[i];}delete del;// 如果删除最高层结点,把头节点的层数也降一下// 可以稍微提高查找效率int i = _head->_nextV.size() - 1;while (i >= 0){if (!_head->_nextV[i]){i--;}else{break;}}_head->_nextV.resize(i + 1);return true;}// SkipList精髓vector<Node*> FindPrevNode(int num){Node* cur = _head;int level = _head->_nextV.size() - 1;// 插入位置每一层前一个结点指针vector<Node*> preV(level + 1, _head);while (level >= 0){if (cur->_nextV[level] && num > cur->_nextV[level]->_val){// 目标值比下一个结点值大,向右走cur = cur->_nextV[level];}else if (!cur->_nextV[level] || num <= cur->_nextV[level]->_val){preV[level--] = cur;}}return preV;}// v1.0 Cint RandomLevel(){size_t level = 1;// rand() / RAND_MAX -> [0, 1]while (rand() <= RAND_MAX * _p && level <= _maxLevel){level++;}return level;}// v2.0 C++// int RandomLevel()// {// static std::default_random_engine generator(std::chrono::system_clock::now().time_since_epoch().count());// static std::uniform_real_distribution<double> distribution(0.0, 1.0);// size_t level = 1;// while (distribution(generator) <= _p && level < _maxLevel)// {// ++level;// }// return level;// }
private:Node* _head;size_t _maxLevel = 32;double _p = 0.5;
};
4.SkipList VS 平衡搜索树 && Hash
- SkipList相比平衡搜索树(AVL树和红黑树),都可以做到遍历数据有序,时间复杂度也差不多
- SkipList的优势:
- SkipList实现简单,容易控制
- 平衡树增删查改遍历都更复杂
- SkipList的额外空间消耗更低
- 平衡树节点存储每个值有三叉链,平衡因子/颜色等消耗
- SkipList中 p = 1 / 2 p=1/2 p=1/2时,每个节点所包含的平均指针数目为2
- SkipList中 p = 1 / 4 p=1/4 p=1/4时,每个节点所包含的平均指针数目为1.33
- SkipList实现简单,容易控制
- SkipList的优势:
- SkipList相比哈希表而言,就没有那么大的优势了
- SkipList劣势:
- 哈希表平均时间复杂度是 O(1),比SkipList快
- 哈希表空间消耗略多一点
- SkipList优势:
- 遍历数据有序
- SkipList空间消耗略小一点,哈希表存在链接指针和表空间消耗
- 哈希表扩容有性能损耗
- 哈希表在极端场景下哈希冲突高,效率下降厉害,需要红黑树补足接力
- SkipList劣势:
相关文章:
[C++][数据结构][跳表]详细讲解
目录 0.什么是跳表?1.SkipList的优化思路2.SkipList的效率如何保证?3.SkipList实现4.SkipList VS 平衡搜索树 && Hash 0.什么是跳表? SkipList本质上也是一种查找结构,用于解决算法中的查找问题,跟平衡搜索树…...
tinyxml
github下载相关的软件包,其中有四个文件需要主要需要关注就是分别是tinyxml12.cpp,tinyxml12.h,rss网页xml文件,还有就是官方给的test文件tinyxmltest.cpp。 example1就是提供一个打开文件的方式 int example_1() {XMLDocument …...
Docker(三)-Docker常用命令
1.run run命令执行流程:2.帮助启动类命令 2.1 启动docker systemctl start docker2.2 停止docker systemctl stop docker2.3 重启docker systemctl restart docker2.4查看docker状态 systemctl status docker2.5开机启动 systemctl enable docker2.6查看docker概要信息 …...
[MRCTF2020]PixelShooter
一个apk文件 jeb打开发现是apk文件 apk游戏逆向必须知道的知识: 一般关键数据在 Assets/bin/data/managed/assembly-csharp.dll这个文件里面 我不知道jeb为什么这里我没有 apk是个压缩包 直接解压 这个文件解压也可以发现flag {Unity_1S_Fun_233}...
vue实现的商品列表网页
一、商品列表效果如下 二、代码; vue实现的商品列表网页 , 图片在vue项目的Public文件夹里的 imgs中 <template><div class"common-layout"><!-- el-container:外层容器。 当子元素中包含 <el-header> 或 <el-foo…...
【泛微系统】e-cology非标配功能概览
关于泛微非标功能的功能编号、功能名称及支持版本 编号名称支持版本001考勤功能4.500.0124-9.00+KB900190206002短信通用接口5.000.0327+KB50001003 及以上版本004计划任务接口5.0+KB50001003及以上版本005集成登录接口6.0及以上版本006流程中自定义浏览框5.0+KB50001003及以上…...
Python基础教程(二十八):pip模块
💝💝💝首先,欢迎各位来到我的博客,很高兴能够在这里和您见面!希望您在这里不仅可以有所收获,同时也能感受到一份轻松欢乐的氛围,祝你生活愉快! 💝Ὁ…...
通信系统概述
1.定义 通信系统(也称为通信网络)是利用各种通信线路将地理上分散的、具有独立功能的计算机系统和通信设备按不同的形式连接起来,依靠网络软件及通信协议实现资源共享和信息传递的系统。 2.概述 随着通信技术和网络技术的不断发展ÿ…...
http发展史(http0.9、http1.0、http1.1、http/2、http/3)详解
文章目录 HTTP/0.9HTTP/1.0HTTP/1.1队头阻塞(Head-of-Line Blocking)1. TCP 层的队头阻塞2. HTTP/1.1 的队头阻塞 HTTP/2HTTP/3 HTTP/0.9 发布时间:1991年 特点: 只支持 GET 方法没有 HTTP 头部响应中只有 HTML 内容࿰…...
Hadoop 面试题(四)
1. 简述Hadoop节点的动态上线下线的大概操作 ? 在Hadoop集群中,节点的动态上下线指的是在不停止整个集群服务的情况下,添加或移除节点。这种能力对于维护和扩展集群非常重要。以下是Hadoop节点动态上线下线的大概操作步骤: 动态…...
绽放光彩的小程序 UI 风格
绽放光彩的小程序 UI 风格...
电脑文件夹怎么加密?文件夹加密的5种方法
在数字化时代,信息安全显得尤为重要。对于个人电脑用户来说,文件夹加密是一种有效保护隐私和数据安全的方法。本文将介绍五种文件夹加密的方法,帮助您更好地保护自己的重要文件。 如何设置文件夹密码方法一:利用Windows系统自带的…...
异步复位同步释放
目录 描述 输入描述: 输出描述: 参考代码 描述 题目描述: 请使用异步复位同步释放来将输入数据a存储到寄存器中,并画图说明异步复位同步释放的机制原理 信号示意图: clk为时钟 rst_n为低电平复位 d信号输入…...
JupyterLab使用指南(七):JupyterLab使用 LaTeX 生成数学公式
在 JupyterLab 中,可以使用 LaTeX 语法生成复杂的数学公式。JupyterLab 内置对 LaTeX 的支持,使得我们可以方便地在 notebook 中编写和展示数学公式。以下是详细的步骤和示例。 1. 使用 LaTeX 生成数学公式 LaTeX 是一种专门用于排版数学公式的语言。J…...
docker 环境部署
1.Redis部署 用docker拉取redis镜像 docker pull redis 用docker查看拉取的镜像版本号,这里查到的是 6.2.6 版本 docker inspect redis 通过wget指令下载对应版本的tar包,下载完成后解压 wget https://download.redis.io/releases/redis-6.2.6.tar.gz …...
Spring中的ContextPath总结
Spring中的ContextPath总结 大家好,我是免费搭建查券返利机器人省钱赚佣金就用微赚淘客系统3.0的小编,也是冬天不穿秋裤,天冷也要风度的程序猿! 1. ContextPath的概念 在Spring中,ContextPath是指Web应用程序的上下文…...
C++设计模式——Composite组合模式
一,组合模式简介 真实世界中,像企业组织、文档、图形软件界面等案例,它们在结构上都是分层次的。将系统分层次的方式使得统一管理和添加不同子模块变得容易,在软件开发中,组合模式的设计思想和它们类似。 组合模式是…...
Android提供的LruCache类简介(1)
* If your cached values hold resources that need to be explicitly released, * override {link #entryRemoved}. * 如果你cache的某个值需要明确释放,重写entryRemoved() * If a cache miss should be computed on demand for the corresponding keys, * ov…...
【分布式系列】分布式锁timeout了怎么办?
💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…...
System.getProperty()方法总结
System.getProperty()方法总结 大家好,我是免费搭建查券返利机器人省钱赚佣金就用微赚淘客系统3.0的小编,也是冬天不穿秋裤,天冷也要风度的程序猿!System.getProperty()方法是Java中用于获取系统属性的方法之一。它允许我们访问J…...
大型语言模型在AMD GPU上的推理优化
Large language model inference optimizations on AMD GPUs — ROCm Blogs 大型语言模型(LLMs)已经改变了自然语言处理和理解,促进了在多个领域中的众多人工智能应用。LLMs在包括AI助手、聊天机器人、编程、游戏、学习、搜索和推荐系统在内的…...
Apple - Core Foundation Design Concepts
本文翻译整理自:Core Foundation Design Concepts(更新日期:2013-12-16 https://developer.apple.com/library/archive/documentation/CoreFoundation/Conceptual/CFDesignConcepts/CFDesignConcepts.html#//apple_ref/doc/uid/10000122i 文章…...
lua中的lfs库介绍
lua中的lfs库介绍 说明常用函数解析lfs.attributeslfs.chdirlfs.currentdirlfs.dirlfs.mkdirlfs.rmdirlfs.locklfs.touchlfs.linklfs.setmodelfs.symlinkattributes 说明 lfs是lua中的一个文件系统库,提供了更多高级的文件和目录操作功能,使得lua可以更方…...
PyCharm 快捷键积累
1、快速格式化:Ctrl Alt L Ctrl Alt L 快捷键在 PyCharm 中是用于格式化代码的,它不仅仅适用于 HTML 代码,而是适用于多种编程和标记语言。...
C++进阶之AVL树
个人主页:点我进入主页 专栏分类:C语言初阶 C语言进阶 数据结构初阶 Linux C初阶 C进阶 算法 欢迎大家点赞,评论,收藏。 一起努力,一起奔赴大厂 目录 一.前言 二.插入 三.旋转 3.1右旋 …...
sizeof 和 strlen 比较
sizeof 和 strlen 在 C 语言中都是用于获取某种“大小”的,但它们之间有着显著的区别。 sizeof sizeof 是一个运算符,用于计算数据类型或对象在内存中的大小(以字节为单位)。它可以在编译时确定结果,因为它计算的是类…...
音视频开发—FFmpeg 打开摄像头进行RTMP推流
实验平台:Ubuntu20.04 摄像头:普通USB摄像头,输出格式为YUV422 1.配置RTMP服务器推流平台 使用Nginx 配置1935端口即可,贴上教程地址 ubuntu20.04搭建Nginxrtmp服务器) 2.配置FFmpeg开发环境 过程较为简单,这里不…...
D触发器(D Flip-Flop)与D锁存器(D Latch)
1 基础概念 我们先来简单回顾一下D触发器(D flip-flop)和D锁存器(D latch)的概念,以及它们在数字电路中的作用。 1.1 D触发器(D Flip-Flop) D触发器是一种数字存储器件,它在时钟信号…...
JDK19特性
JDK19特性 一、JAVA19概述 JDK 19 2022 年 9 月 20 日正式发布以供生产使用,非长期支持版本。不过,JDK 19 中有一些比较重要的新特性值得关注。 JDK 19 只有 7 个新特性: JEP 405: Record Patterns(记录模式)[1] (预览)JEP 422: Linux/RISC-V Port[2]JEP 424: Foreign …...
sql语句中常用的函数有那些
1、字符串函数 CONCAT(string1, string2, ...): 连接两个或多个字符串。 UPPER(string): 将字符串转换为大写。 LOWER(string): 将字符串转换为小写。 TRIM(string): 去除字符串两端的空格。 LENGTH(string): 返回字符串的长度。 SUBSTRING(string, start, length): 从字符串中…...
odoo17 小变更3 Warning、 “attrs “和 “states “不再用
odoo17 小变更 1、Warning from odoo.exceptions import ValidationError,Warning ImportError: cannot import name Warning from odoo.exceptions (D:\od172406\odoo\exceptions.py) 2、自 17.0 版起,不再使用 "attrs "和 "states "属性。 …...
Unity3d 游戏暂停(timeScale=0)引起的deltaTime关联的系列问题解决
问题描述 游戏暂停的功能是通过设置timeScale0实现的,不过在暂停游戏的时候,需要对角色进行预览和设置,为了实现这个功能,是通过鼠标控制相机的操作,为了使相机的操作丝滑,获取鼠标操作系数乘以Time.delta…...
服务端代码编写中MySql大小写在Java中报错问题解决
报错信息: 原因:MySql和Java变量大小写产生的冲突。 经过查阅各个博客等,得出浅显结论(不一定对):MySql大小写不敏感,Java大小写敏感,当Javabean转为MySql数据库表时,Ja…...
CRMEB 多店商品详情页装修说明
一、功能介绍 商家可调整商品详情各板块样式,可根据不同的需求开启或关闭单独的板块 二、操作流程 装修 > 商品详情 三、功能说明 1、商品信息 可控制商品详情页面商品信息的显示与隐藏 2、会员信息,排行榜 控制商品详情页面会员信息及排行榜的…...
Redis-使用 jedis 操作数据
文章目录 1、Jedis简介2、环境准备3、创建maven普通项目,导入如下依赖4、测试JAVA程序和Redis之间的通信 1、Jedis简介 "Jedis" 通常是作为 "Java Redis" 的缩写或简称来理解的。Java Embedded Data Structures Interface 表示 Java嵌入式数据结构接口 2、…...
简说PIP换源
概述 PIP(Python Package Installer)是 Python 的包管理工具,用于安装和管理 Python 包。默认情况下,PIP 从 Python 官方的包仓库(即 PyPI)下载和安装包。然而,由于网络原因,访问官…...
django学习入门系列之第三点《CSS基础样式介绍2》
文章目录 文字对齐方式外边距内边距往期回顾 文字对齐方式 水平对齐方式 text-align: center;垂直对齐方式 /* 注意,这个只能是一行来居中 */ line-height:/*长度*/ ;样例 <!DOCTYPE html> <html lang"en"> <head><meta charset…...
分布式光纤测温DTS在工程现场中稳定性与可靠性如何?
20年前,分布式光纤测温(Distributed Temperature Sensing,DTS)技术的发展尚不成熟,设备成本高昂,其稳定性与可靠性也存在一定问题。然而,经过二十多年的不断发展与创新,DTS技术在工程现场应用中取得了显著进…...
PHP多线程模块parallel的编译安装和多线程编程演示
从PHP7开始,多线程编原有的pthreads已经不在维护,而是使用parallel替代。 由于是新的模块,样例代码很少,这里总结一个简单的代码和详细的备注供大家参考。 编译和安装 parallel需要启用ZTS(Zend Thread Safety&…...
记录grid布局属性
grid布局 分为容器和项目元素 容器属性 #container{display:grid;grid-template-columns:100px 100px 100px;/* 1fr 表示比例为占1份 */grid-template-columns:1fr 100px 1fr;/*100px为1列,自动填充,容器宽度不足则换行*/grid-template-columns:repeat(auto-fill,100px);/* …...
12.爬虫---PyMysql安装与使用
12.PyMysql安装与使用 1.安装 PyMySQL2.使用PyMySQL2.1创建数据表2.2连接数据库2.3增加数据2.4修改数据2.5查询数据2.6删除数据2.7关闭连接 3.总结 MySQL 安装可以看这篇文章MySql 安装与使用(非常详细) 1.安装 PyMySQL PyMySQL是Python中用于连接MySQL…...
VS2022遇到的两个问题
问题一:找不到定义的头文件 别的博主说是:在属性页里面进行改写,改成是,我试过之后并不行; 解决思路:但其实在右边视图里面找到你自己定义的头文件加到你运行文件中就行;因为程序就只有一个入口…...
【Android14 ShellTransitions】(六)SyncGroup完成
这一节的内容在WMCore中,回想我们的场景,是在Launcher启动某一个App,那么参与动画的就是该App对应Task(OPEN),以及Launcher App对应的Task(TO_BACK)。在确定了动画的参与者后&#x…...
技术管理转型之战:决策之道-管理中的智慧与策略
文章目录 引言一、决策的重要性二、常见的决策方式1. 理性决策(Rational Decision Making)2. 有限理性(Bounded Rationality)3. 直觉决策(Intuitive Decision Making)4. 循证管理(Evidence-Base…...
Shell脚本:条件语句(if、case)
目录 硬编码 硬编码的缺点 条件判断 $? 命令行语句 判断指定目录是否存在 判断指定文件是否存在 判断指定对象是否存在 表达式形式语句 判断对象是否存在 判断对象是否有权限 与、或、非 运算 与运算 或运算 非运算 比较大小 判断磁盘利用率实验步骤 字符串…...
在Linux上为Windows目标配置Qt交叉编译
问题描述 我想使用Linux x86_64主机为Windows x86_64目标交叉编译Qt库(最终也包括我的应用程序)。我觉得自己已经接近成功了,但可能对整个过程有一些基本的误解。 我从在我的Fedora机器上安装所有mingw包开始,并修改了win32-g的…...
Introduction to linear optimization 第 2 章课后题答案 11-15
线性规划导论 Introduction to linear optimization (Dimitris Bertsimas and John N. Tsitsiklis, Athena Scientific, 1997), 这本书的课后题答案我整理成了一个 Jupyter book,发布在网址: https://robinchen121.github.io/manual-introdu…...
Java——包
一、包 1、简要介绍 在Java编程语言中,包(Package) 是一种用来组织和管理类(Class)和接口(Interface)的机制。包为开发者提供了一种逻辑分组的方式,使代码更加模块化、结构化和易于…...
Pipeline知识小记
在scikit-learn(通常缩写为sklearn)中,Pipeline是一个非常重要的工具,它允许你将多个数据转换步骤(如特征选择、缩放等)和估计器(如分类器、回归器等)组合成一个单一的估计器对象。这…...
postman国内外竞争者及使用详解分析
一、postman简介 Postman 是一款广泛使用的 API 开发和测试工具,适用于开发人员和测试人员。它提供了一个直观的界面,用于发送 HTTP 请求、查看响应、创建和管理 API 测试用例,以及自动化 API 测试工作流程。以下是 Postman 的主要功能和特点…...