有趣的算法(二)——跳跃表的分析

有趣的算法(二)——跳跃表的分析

(原创内容,转载请注明来源,谢谢)

一、概述

最近在学习redis,其中说到当使用redis的sorted set类型时,如果数据量大,redis内部会使用跳跃表结合散列表的方式对数据进行存储。其中散列表主要用在存储score,即hash的方式——键值对。而由于sorted set的值按照score有序排序,因此跳跃表用于存储score和内容的对应关系。

二、理想跳跃表的存储

跳跃表是一种改进的链表,理想的跳跃表如下图:

从图中可以看到,跳跃表通过增加存储,来达到查询时的类二分法。理想跳跃表,第一层的数字是从小到大排序,第二层存储了第一层每两个中的一个,第三层存第二层每两个中的一个,以此类推,最后一层存储2个。另外,除了第一层,其余每一层每一个元素都指向下一层中和本元素值相同的元素。

这样做的好处在于,查询的时候可以从最高层开始查找,从小到大,当匹配到小于目标值的最大值时,进入下一层进行查找,以此类推,直到找到结果或确定结果不存在。

三、redis中sorted set的值存储

类似跳跃表,但是为了方便逆向排序,对每个元素加入了指向前一个元素的指针。另外根据sorted set特性,允许跳跃表中的元素值相同。

四、类理想跳跃表

理想跳跃表对于查找来说实现完全的二分法,速度最快。但是,当元素插入、删除时,如果仍使用理想跳跃表,维护起来极其复杂。因此,通常采用类理想跳跃表,即非理想情况下的最优,而又最利于元素的插入和删除。

观察理想跳跃表,发现高层元素的个数总是下一层元素的一半。现采用概率的方式,第一层所有新增的数据全部加入,第二层开始,当第一层元素插入后的,其的前后都没有对应的第二层的元素指向,则在第二层直接加入;如果前后都有,则不加入;如果前后有一个指向,则用随机的方式,如果随机出值,就在第二层进行增加,否则不增加。高层类推。

此方法在数据量小的时候,偏差较大,而当数据量非常大的时候,由于总是0.5的几率插入,因此概率上是一个接近完美的跳跃表。

因此,数据量小的时候,不适合使用跳跃表,因为n很小的时候,O(1)和O(n)差距不大。当数据量大的时候,由于类理想跳跃表又接近于理想跳跃表,则可以很好的使用。

——written by linhxx 2017.08.07

原文发布于微信公众号 - 决胜机器学习(phpthinker)

原文发表时间:2017-08-07

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏C语言及其他语言

【每日一题】

笨小猴的词汇量很小,所以每次做英语选择题的时候都很头疼。但是他找到了一种方法,经试验证明,用这种方法去选择选项的时候选对的几率非常大! 这种方法的具体描述如下:...

912
来自专栏尾尾部落

[剑指offer] 调整数组顺序使奇数位于偶数前面

输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相...

742
来自专栏灯塔大数据

每周学点大数据 | No.20序列有序的判定

No.19期 序列有序的判定0 数组的判 Mr. 王:这里我们再讲一个亚线性时间的判定问题——数组有序的判定问题。你来说一下问题定义,并想一想这个问题...

2675
来自专栏码云1024

Numpy 运算

最简单的数值计算时数组和标量进行计算,计算过程是直接把数组里的元素和标量逐个进行计算:

33916
来自专栏ATYUN订阅号

【学术】独热编码如何在Python中排列数据?

机器学习算法不能直接处理分类数据,分类数据必须转换为数字。这适用于当你处理一个序列分类类型的问题,并计划使用深度学习方法,比如长短期循环神经网络(RNN)时。 ...

36310
来自专栏Python小屋

一维序列卷积之Python实现

在数字信号处理中经常会用到卷积计算,例如各种滤波器的设计。两个序列的卷积计算大体需要3步: 1)翻转其中一个序列; 2)移动翻转后的序列,并计算每次移动后两个序...

3359
来自专栏武培轩的专栏

剑指Offer-调整数组顺序使奇数位于偶数前面

题目描述 输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于位于数组的后半部分,并保证奇数和奇数,偶数和偶...

3426
来自专栏数据科学与人工智能

【Python环境】Python Numpy数组及矩阵线性运算

numpy中数组的运算基本分为数组与标量的运算和数组之间的运算(线性运算)。 一、数组和标量之间的运算 数组与标量之间的运算采用的是矢量化运算,它可...

2178
来自专栏CDA数据分析师

Python之numpy数组学习(二)

前言 前面我们学习了numpy库的简单应用,今天来学习下比较重要的如何处理数组。 处理数组形状 下面可将多维数组转换成一维数组时的情形。 利用以下函数处理数组的...

1778
来自专栏mukekeheart的iOS之旅

如何求最小三元组距离

题目描述:   已知三个升序整数数组a[l], b[m]和c[n]。请在三个数组中各找一个元素,使得组成的三元组距离最小。   三元组的距离定义是:假设a[i]...

2198

扫码关注云+社区