当前位置: 首页 > news >正文

数据结构——跳表

目录

1.什么是跳表-skiplist

2.skiplist的效率如何保证?

3.skiplist的实现

4.skiplist跟平衡搜索树和哈希表的对比


1.什么是跳表-skiplist

        skiplist本质上也是一种查找结构,用于解决算法中的查找问题,跟平衡搜索树和哈希表的价值是一样的,可以作为key或者key/value的查找模型。那么相比而言它的优势是什么的呢?这么等我们学习完它的细节实现,我们再来对比

        skiplist是由William Pugh发明的,最早出现于他在1990年发表的论文《Skip Lists: A Probabilistic Alternative to Balanced Trees》

        skiplist,顾名思义,首先它是一个list。实际上,它是在有序链表的基础上发展起来的。如果是一个有序的链表,查找数据的时间复杂度是O(N)

William Pugh开始的优化思路:

  1. 假如我们每相邻两个节点升高一层,增加一个指针,让指针指向下下个节点,如下图b所 示。这样所有新增加的指针连成了一个新的链表,但它包含的节点个数只有原来的一半。由 于新增加的指针,我们不再需要与链表中每个节点逐个进行比较了,需要比较的节点数大概 只有原来的一半
  2. 以此类推,我们可以在第二层新产生的链表上,继续为每相邻的两个节点升高一层,增加一 个指针,从而产生第三层链表。如下图c,这样搜索效率就进一步提高了
  3. skiplist正是受这种多层链表的想法的启发而设计出来的。实际上,按照上面生成链表的方 式,上面每一层链表的节点个数,是下面一层的节点个数的一半,这样查找过程就非常类似 二分查找,使得查找的时间复杂度可以降低到O(log n)。但是这个结构在插入删除数据的时 候有很大的问题,插入或者删除一个节点之后,就会打乱上下相邻两层链表上节点个数严格 的2:1的对应关系。如果要维持这种对应关系,就必须把新插入的节点后面的所有节点(也 包括新插入的节点)重新进行调整,这会让时间复杂度重新蜕化成O(n)

        

        4.skiplist的设计为了避免这种问题,做了一个大胆的处理,不再严格要求对应比例关系,而是            插入一个节点的时候随机出一个层数。这样每次插入和删除都不需要考虑其他节点的层数,            这样就好处理多了。细节过程入下图:

2.skiplist的效率如何保证?

        上面我们说到,skiplist插入一个节点时随机出一个层数,听起来怎么这么随意,如何保证搜索时的效率呢?

        这里首先要细节分析的是这个随机层数是怎么来的。一般跳表会设计一个最大层数maxLevel的限 制,其次会设置一个多增加一层的概率p。那么计算这个随机层数的伪代码如下图:

在Redis的skiplist实现中,这两个参数的取值为:

p = 1/4
maxLevel = 32

        根据前面randomLevel()的伪码,我们很容易看出,产生越高的节点层数,概率越低。定量的分析如下:

  • 节点层数至少为1。而大于1的节点层数,满足一个概率分布
  • 节点层数恰好等于1的概率为1-p
  • 节点层数大于等于2的概率为p,而节点层数恰好等于2的概率为p(1-p)
  • 节点层数大于等于3的概率为p^2,而节点层数恰好等于3的概率为p^2*(1-p)
  • 节点层数大于等于4的概率为p^3,而节点层数恰好等于4的概率为p^3*(1-p)
  • 以此类推

因此,一个节点的平均层数(也即包含的平均指针数目),计算如下:

现在很容易计算出:

  • 当p=1/2时,每个节点所包含的平均指针数目为2
  • 当p=1/4时,每个节点所包含的平均指针数目为1.33

        跳表的平均时间复杂度为O(logN),这个推导的过程较为复杂,需要有一定的数学功底

3.skiplist的实现

我们通过一道题来实现跳表

https://leetcode.cn/problems/design-skiplist/description/

        对于跳表的查找,我们首先将查找值与当前节点的值比较,如果比当前值大就想右走,如果小就向下走,同时也应该注意如果下一个节点为空的话也要向下走

bool search(int target) {Node* cur = _head;int level = _head->_nextV.size() - 1;while(level >= 0){//下一个节点不为空且查找值比下一个节点的值大,向右走//下一个节点为空或者查找值比下一个节点的值小,向下走if(cur->_nextV[level] && cur->_nextV[level]->_val < target){//向右走cur = cur->_nextV[level];}else if(cur->_nextV[level] == nullptr || cur->_nextV[level]->_val > target){//向下走--level;}else{return true;}    }return false;}

        跳表的层数我们通过公式来进行控制层数出现的概率

int RandomLevel(){size_t level = 1;while(rand() < RAND_MAX*_p && level < _maxLevel){++level;}return level;}

        跳表的插入我们首先需要判断究竟插入在哪一层,而对于删除时也需要判断删除值的层数,所以直接写成一个函数方便调用,减少代码的冗余性

vector<Node*> FindPrevNode(int num){Node* cur = _head;int level = _head->_nextV.size() - 1;vector<Node*> prevV(level + 1, _head);while(level >= 0){if(cur->_nextV[level] && cur->_nextV[level]->_val < num){//向右走cur = cur->_nextV[level];}else if(cur->_nextV[level] == nullptr || cur->_nextV[level]->_val >= num){//更新level层前一个节点,向下走prevV[level]=cur;--level;}}return prevV;}
void add(int num) {vector<Node*> prevV = FindPrevNode(num);int n = RandomLevel();Node* newnode = new Node(num, n);//如果n大于当前层数,就升高if(n > _head->_nextV.size()){_head->_nextV.resize(n, nullptr);prevV.resize(n, _head);}//链接前后节点for(size_t i =0; i < n; ++i){newnode->_nextV[i] = prevV[i]->_nextV[i];prevV[i]->_nextV[i] = newnode;}}

        跳表删除时只需要整体遍历即可,同时我们还可以对其进行一些小的优化,如果删除了最高层的节点的话,我们将层数下降,可以提高效率

bool erase(int num) {vector<Node*> prevV = FindPrevNode(num);if(prevV[0]->_nextV[0] == nullptr || prevV[0]->_nextV[0]->_val != num){return false;}else{Node* del = prevV[0]->_nextV[0];for(size_t i = 0; i < del->_nextV.size(); ++i){prevV[i]->_nextV[i] = del->_nextV[i];}delete del;//删除最高层节点,将头节点层数下降int i = _head->_nextV.size() - 1;while(i >= 0){if(_head->_nextV[i] == nullptr)--i;elsebreak;}_head->_nextV.resize(i + 1);return true;}}

        我们可以写出输出函数来查看结果,写oj题时不需要,这里只是为了进一步理解跳表的结构

void Print(){int level = _head->_nextV.size();for(int i = level - 1; i >= 0; --i){Node* cur = _head;while(cur){printf("%d->", cur->_val);cur = cur->_nextV[i];}printf("\n");}}
struct SkiplistNode
{int _val;vector<SkiplistNode*> _nextV;SkiplistNode(int val,int level):_val(val), _nextV(level,nullptr){ }
};class Skiplist {typedef SkiplistNode Node;
public:Skiplist() {//头节点,层数为1_head = new SkiplistNode(-1, 1);}bool search(int target) {Node* cur = _head;int level = _head->_nextV.size() - 1;while(level >= 0){//下一个节点不为空且查找值比下一个节点的值大,向右走//下一个节点为空或者查找值比下一个节点的值小,向下走if(cur->_nextV[level] && cur->_nextV[level]->_val < target){//向右走cur = cur->_nextV[level];}else if(cur->_nextV[level] == nullptr || cur->_nextV[level]->_val > target){//向下走--level;}else{return true;}    }return false;}vector<Node*> FindPrevNode(int num){Node* cur = _head;int level = _head->_nextV.size() - 1;vector<Node*> prevV(level + 1, _head);while(level >= 0){if(cur->_nextV[level] && cur->_nextV[level]->_val < num){//向右走cur = cur->_nextV[level];}else if(cur->_nextV[level] == nullptr || cur->_nextV[level]->_val >= num){//更新level层前一个节点,向下走prevV[level]=cur;--level;}}return prevV;}void add(int num) {vector<Node*> prevV = FindPrevNode(num);int n = RandomLevel();Node* newnode = new Node(num, n);//如果n大于当前层数,就升高if(n > _head->_nextV.size()){_head->_nextV.resize(n, nullptr);prevV.resize(n, _head);}//链接前后节点for(size_t i =0; i < n; ++i){newnode->_nextV[i] = prevV[i]->_nextV[i];prevV[i]->_nextV[i] = newnode;}}bool erase(int num) {vector<Node*> prevV = FindPrevNode(num);if(prevV[0]->_nextV[0] == nullptr || prevV[0]->_nextV[0]->_val != num){return false;}else{Node* del = prevV[0]->_nextV[0];for(size_t i = 0; i < del->_nextV.size(); ++i){prevV[i]->_nextV[i] = del->_nextV[i];}delete del;//删除最高层节点,将头节点层数下降int i = _head->_nextV.size() - 1;while(i >= 0){if(_head->_nextV[i] == nullptr)--i;elsebreak;}_head->_nextV.resize(i + 1);return true;}}int RandomLevel(){size_t level = 1;while(rand() < RAND_MAX*_p && level < _maxLevel){++level;}return level;}void Print(){int level = _head->_nextV.size();for(int i = level - 1; i >= 0; --i){Node* cur = _head;while(cur){printf("%d->", cur->_val);cur = cur->_nextV[i];}printf("\n");}}
private:Node* _head;size_t _maxLevel=32;double _p=0.25;
};

4.skiplist跟平衡搜索树和哈希表的对比

  1. skiplist相比平衡搜索树(AVL树和红黑树)对比,都可以做到遍历数据有序,时间复杂度也差 不多。skiplist的优势是:a、skiplist实现简单,容易控制。平衡树增删查改遍历都更复杂。 b、skiplist的额外空间消耗更低。平衡树节点存储每个值有三叉链,平衡因子/颜色等消耗。 skiplist中p=1/2时,每个节点所包含的平均指针数目为2;skiplist中p=1/4时,每个节点所包 含的平均指针数目为1.33
  2. skiplist相比哈希表而言,就没有那么大的优势了。相比而言a、哈希表平均时间复杂度是 O(1),比skiplist快。b、哈希表空间消耗略多一点。skiplist优势如下:a、遍历数据有序 b、skiplist空间消耗略小一点,哈希表存在链接指针和表空间消耗。c、哈希表扩容有性能损 耗。d、哈希表极端场景下哈希冲突高,效率下降厉害,需要红黑树来补足缺点

相关文章:

数据结构——跳表

目录 1.什么是跳表-skiplist 2.skiplist的效率如何保证&#xff1f; 3.skiplist的实现 4.skiplist跟平衡搜索树和哈希表的对比 1.什么是跳表-skiplist skiplist本质上也是一种查找结构&#xff0c;用于解决算法中的查找问题&#xff0c;跟平衡搜索树和哈希表的价值是一样的…...

活动预告 |【Part2】Microsoft Azure 在线技术公开课:基础知识

课程介绍 参加“Azure 在线技术公开课&#xff1a;基础知识”活动&#xff0c;培养有助于创造新的技术可能性的技能并探索基础云概念。参加我们举办的本次免费培训活动&#xff0c;扩充自身的云模型和云服务类型知识。你还可以查看以计算、网络和存储为核心的 Azure 服务。 课…...

PyCharm如何导入库( 包 )

目录 1.在主界面中导库 2.用设置->项目安装库 2.1.使用右上方按钮 2.2.使用右下方Python解释器 3.使用左下角终端导库 1.在主界面中导库 在主界面输入导库后等待一会儿&#xff0c;会在那一行出现一个红色灯。 图1 红色灯 我们点击红色灯&#xff0c;会出现 图2 错误选…...

【DevOps基础篇】SCM(Source Code Management)

目录 代码管理工具Git特点:SVN特点:Git与SVN的对比:Git 的开发工作流程(flow)的设计Git Flow主要特点:工作流程:GitHub Flow主要特点:工作流程:两种Flow的对比:推荐超级课程: Docker快速入门到精通Kubernetes入门到大师通关课AWS云服务快速入门实战代码管理工具 Gi…...

DDS—RTPS一致性测试案例分析

1 往期回顾 通过《DDS数据分发服务—提升汽车领域数据传输效率》和《DDS—DCPS测试策略介绍及实际案例分析》这两篇文章的介绍&#xff0c;相信广大读者对Data Distribution Service(DDS)协议和Data Centric Publish Subscribe(DCPS)测试有了基本了解&#xff1a;DDS协议致力于…...

【深度学习入门】深度学习介绍

1.1 深度学习介绍 学习目标 目标 知道深度学习与机器学习的区别了解神经网络的结构组成知道深度学习效果特点 应用 无 区别 特征提取方面 机器学习的特征工程步骤是要靠手动完成的&#xff0c;而且需要大量领域专业知识深度学习通常由多个层组成&#xff0c;它们通常将更简…...

数值分析—非线性方程的数值解

研究背景 形如 x − t a n x 0 x-tanx0 x−tanx0、 x l n x e − x 2 s i n x 0 xlnxe^{-x^2}sinx0 xlnxe−x2sinx0等称为非线性方程&#xff0c;自变量之间并非简单的线性关系&#xff0c;这种问题我们无法通过其结构求解&#xff0c;需要其他的逼近方式&#xff0c;本章…...

LDR6500应用:C转DP线材双向投屏开启全新体验

在当今这个科技日新月异、蓬勃发展的时代&#xff0c;高清视频传输以及显示技术已经深深融入到我们日常生活与工作的方方面面&#xff0c;其重要性不言而喻。不管是在商务场合的会议演示&#xff0c;还是教育领域的娱乐享受&#xff0c;以及充满激情的游戏竞技领域&#xff0c;…...

路径规划之启发式算法之十六:和声搜索算法(Harmony Search, HS)

和声搜索算法(Harmony Search, HS)是一种新兴的启发式全局搜索算法,是一种模拟音乐家即兴演奏过程的群体智能优化算法。这种算法由Zong Woo Geem等人在2001年提出,灵感来源于音乐家在寻找和声时的创造性思维过程。HS算法通过模拟音乐家演奏音乐时的选择过程来寻找问题的最优…...

Redis - 实战之 全局 ID 生成器 RedisIdWorker

概述 定义&#xff1a;一种分布式系统下用来生成全局唯一 ID 的工具 特点 唯一性&#xff0c;满足优惠券需要唯一的 ID 标识用于核销高可用&#xff0c;随时能够生成正确的 ID高性能&#xff0c;生成 ID 的速度很快递增性&#xff0c;生成的 ID 是逐渐变大的&#xff0c;有利于…...

matlab 连接远程服务器

通过matlab 控制远程服务器 查看 matlab 中 python 接口脚本 对于 matlab 2010b 兼容的 最高 Python版本是 3.10 安装 3.10 版本的Python&#xff0c;并安装 paramiko 库 pip install paramikomatlab 中设置 Python的环境 例如 pyversion&#xff08;D:/Anaconda3/python.e…...

在服务器自主选择GPU使用

比如说&#xff0c;程序使用第 2 张显卡&#xff08;从 0 开始计数&#xff09;。它的作用是告诉系统和深度学习框架&#xff08;如 PyTorch 或 TensorFlow&#xff09;只可见某些 GPU。 export CUDA_VISIBLE_DEVICES1 然后再查看当前使用的显卡&#xff1a; echo $CUDA_VIS…...

【设计模式】享元模式(Flyweight Pattern)

享元模式&#xff08;Flyweight Pattern&#xff09;是一种结构型设计模式&#xff0c;它通过共享尽可能多的对象来有效支持大量细粒度的对象。这个模式主要用于减少内存使用和提高性能&#xff0c;特别是在需要创建大量相似对象的场景中。享元模式的核心思想是将对象的状态分为…...

题目 1688: 数据结构-字符串插入

第一种方式字符串 #include<iostream> #include<cstring> #include<algorithm> using namespace std; int main(){string s1,s2;int n;cin>>s1>>s2>>n;s1.insert(n-1,s2);cout<<s1<<endl;return 0; } 第二种方式字符数组 …...

28.攻防世界PHP2

进入场景 扫描目录 [04:12:32] 403 - 303B - /.ht_wsr.txt [04:12:32] 403 - 306B - /.htaccess.bak1 [04:12:32] 403 - 308B - /.htaccess.sample [04:12:…...

QML QT6 WebEngineView 、Echarts使用和数据交互

QML 中的 WebEngineView 是用于显示网页内容的组件,它基于 Qt WebEngine,支持现代网页渲染和与 JavaScript 的交互。它通常用来在 QML 应用中嵌入浏览器或加载在线资源。WebEngineView 可以展示 HTML、CSS、JavaScript 等网页内容,并提供多种属性和方法来控制其行为。 如下…...

SpringBoot 整合 Mail 轻松实现邮件自动推送

简单使用 1、pom 包配置 pom 包里面添加 spring-boot-starter-mail 包引用 <dependencies><dependency> <groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-mail</artifactId></dependency> </de…...

MyBatis 核心知识与实践

一、MyBatis 概述 1. 框架简介 MyBatis 是一款支持自定义 SQL、存储过程以及高级映射的持久层框架。它避免了几乎所有的 JDBC 代码和手动设置参数以及获取结果集的操作&#xff0c;使开发人员能够更专注于 SQL 语句的编写和业务逻辑的处理。 2. 核心组件 SqlSessionFactoryB…...

机器学习期末速成

文章目录 一、机器学习分类二、逻辑回归三、决策树四、集成学习算法五、支持向量机六、聚类七、特征工程和指标 文章参考自B站机器学习期末速成课 本文仅作者个人复习使用 一、机器学习分类 聚类和分类的区别&#xff1a; 分类&#xff1a;一开始就知道有哪些类别 聚类&#…...

Linux中的线程

目录 线程的概念 进程与线程的关系 线程创建 线程终止 线程等待 线程分离 原生线程库 线程局部存储 自己实现线程封装 线程的优缺点 多线程共享与独占资源 线程互斥 互斥锁 自己实现锁的封装 加锁实现互斥的原理 死锁 线程同步 线程的概念 回顾进程相关概念 …...

AI大模型学习笔记|多目标算法梳理、举例

多目标算法学习内容推荐&#xff1a; 1.通俗易懂讲算法-多目标优化-NSGA-II(附代码讲解)_哔哩哔哩_bilibili 2.多目标优化 (python pyomo pareto 最优)_哔哩哔哩_bilibili 学习笔记&#xff1a; 通过网盘分享的文件&#xff1a;多目标算法学习笔记 链接: https://pan.baidu.com…...

蓝桥杯刷题——day3

蓝桥杯刷题——day3 题目一题干题目解析代码 题目二题干题目解析代码 题目一 题干 每张票据有唯一的 ID 号&#xff0c;全年所有票据的 ID 号是连续的&#xff0c;但 ID 的开始数码是随机选定的。因为工作人员疏忽&#xff0c;在录入 ID 号的时候发生了一处错误&#xff0c;造…...

企业级日志分析系统ELK之ELK概述

ELK 概述 ELK 介绍 什么是 ELK 早期IT架构中的系统和应用的日志分散在不同的主机和文件&#xff0c;如果应用出现问题&#xff0c;开发和运维人员想排 查原因&#xff0c;就要先找到相应的主机上的日志文件再进行查找和分析&#xff0c;所以非常不方便&#xff0c;而且还涉及…...

【开源项目】经典开源项目数字孪生体育馆—开源工程及源码

飞渡科技数字孪生体育馆管理平台&#xff0c;融合物联网IOT、BIM数据模型、三维GIS等技术&#xff0c;实现体育馆的全方位监控和实时全局掌握&#xff0c;同时&#xff0c;通过集成设备设施管理、人员管理等子系统&#xff0c;减少信息孤岛&#xff0c;让场馆“可视、可控、可管…...

C++多线程实战:掌握图像处理高级技巧

文章结尾有最新热度的文章,感兴趣的可以去看看。 本文是经过严格查阅相关权威文献和资料,形成的专业的可靠的内容。全文数据都有据可依,可回溯。特别申明:数据和资料已获得授权。本文内容,不涉及任何偏颇观点,用中立态度客观事实描述事情本身 导读 在当今的计算世界中,…...

解决MAC装win系统投屏失败问题(AMD显卡)

一、问题描述 电脑接上HDMI线后&#xff0c;电脑上能显示有外部显示器接入&#xff0c;但是外接显示器无投屏画面 二、已测试的方法 1 更改电脑分辨&#xff0c;结果无效 2 删除BootCamp&#xff0c;结果无效 3更新电脑系统&#xff0c;结果无效 4 在设备管理器中&#…...

网易游戏分享游戏场景中MongoDB运行和分析实践

在游戏行业中&#xff0c;数据库的稳定和性能直接影响了游戏质量和用户满意度。在竞争激烈的游戏市场中&#xff0c;一个优秀的数据库产品无疑能为游戏的开发和后期的运营奠定良好的基础。伴随着MongoDB在不同类型游戏场景中的应用越来越广泛&#xff0c;许多知名的游戏公司都在…...

Android14 AOSP 允许system分区和vendor分区应用进行AIDL通信

在Android14上&#xff0c;出于种种原因&#xff0c;system分区的应用无法和vendor分区的应用直接通过AIDL的方法进行通信&#xff0c;但是项目的某个功能又需要如此。 好在Binder底层其实是支持的&#xff0c;只是在上层进行了屏蔽。 修改 frameworks/native/libs/binder/Bp…...

R学习——因子

目录 1 定义因子&#xff08;factor函数&#xff09; 2因子的作用 一个数据集中的 只需要考虑可以用哪个数据来进行分类就可以了&#xff0c;可以用来分类就可以作为因子。 Cy1这个因子对应的水平level是4 6 8&#xff1a; 1 定义因子&#xff08;factor函数&#xff09; 要…...

pytest入门三:setup、teardown

https://zhuanlan.zhihu.com/p/623447031 function对应类外的函数&#xff0c;每个函数调用一次 import pytest def setup_module():print(开始 module)def teardown_module():print(结束 module)def setup_function():print(开始 function)def teardown_function():print(结…...

网站设计与网页制作公司/seo 公司

Word是微软Office家族成员之一&#xff0c;Word 提供了丰富的功能供大家使用&#xff0c;深受办公室工作人员的喜爱。哪怕只使用 Word 应用一点文本格式化操作或图片处理&#xff0c;也可以使简单的文档变得比只使用纯文本更具吸引力。今天要给大家分享的就是使用Word快速制作会…...

福州做网站多少钱/搜索大全搜索引擎

sed -n ‘/开始时间日期/,/结束时间日期/p’ nginx.log sed支持正则表达式&#xff0c;比如&#xff0c;查询时间段2021-03-24 10:12:12 到 2021-09-24 10:12:12 可以用sed -n ‘/2021-03-24 10:12:*/,/2021-09-24 10:12:*/p’ nginx.log查询。...

如何做色流量网站/软文代写代发

1. 挂失补卡后的bug bug描述&#xff1a;某用户在进行挂失操作时&#xff0c;选择“是否立即补卡”&#xff0c;如果放在读卡器上的卡是一张已发的卡的话&#xff0c;该用户将造成该用户cardno 的卡库不一致。 原因分析&#xff1a;使用的数据库表&#xff1a;rec_card_make , …...

网站标题怎么改/站长工具seo综合查询 分析

...

做网站申请哪类商标/关键词免费网站

在C11中提供了sdt::thread&#xff0c;可以很方便的让我们对当前的线程进行管理。其中提供了四个成员函数&#xff0c;使用方法和注意事项见代码 #include <thread> #include <chrono> #include <thread> #include <iostream> #include <mutex>…...

网站备案表格下载/什么是seo优化

--实测只有主表动宽表动&#xff0c;从表动主表不动宽表不动 CREATE MATERIALIZED VIEW dws_iot.realtime_device engine CollapsingMergeTree(sign) PARTITION BY toYYYYMM(created_date) order by id POPULATE AS SELECTdv.id AS id,dv.sign AS sign,dv.created_date AS cr…...