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

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

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

一、概述

最近在学习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 条评论
登录 后参与评论

相关文章

来自专栏林欣哲

人工智能的无信息搜索

在人工智能中,当你面对一些问题不知道怎么解决的时候,有一类常用的解决问题的方法,叫做搜索。就好像你在一片迷雾的森林里,不知道怎么办时,走一步算一步,走起来再说。...

2765
来自专栏瓜大三哥

BP神经网络续1

一、BP网络中的函数 1.创建函数 1) cascadeforwardnet函数 cascadeforwardnet(hiddenSizes,trainFcn)...

2299
来自专栏WD学习记录

机器学习 学习笔记(10)序列最小最优化算法

序列最小最优化算法(Sequential minimal optimization)

752
来自专栏瓜大三哥

径向基神经网络续1

一、径向基神经网络的函数 1.创建函数 (1) newrb函数 该函数用于设计一个径向基神经网络: [net,tr]=newrb(P,T,goal,sprea...

2145
来自专栏ATYUN订阅号

重新调整Keras中长短期记忆网络的输入数据

你可能很难理解如何为LSTM模型的输入准备序列数据。你可能经常会对如何定义LSTM模型的输入层感到困惑。也可能对如何将数字的1D或2D矩阵序列数据转换为LSTM...

2104
来自专栏Python小屋

几行Python代码生成饭店营业额模拟数据并保存为CSV文件

CSV文件是一种通用的、简单的文件格式,以纯文本形式存储表格数据(数字和文本),在多个领域都有广泛应用,经常用来在不同程序之间交换数据。 下面的代码使用Pyth...

3489
来自专栏Python小屋

Python使用系统聚类算法对随机元素进行分类

系统聚类算法又称层次聚类或系谱聚类,首先把样本看作各自一类,定义类间距离,选择距离最小的一对元素合并成一个新的类,重复计算各类之间的距离并重复上面的步骤,直到将...

3416
来自专栏李蔚蓬的专栏

第14周Python机器学习周记

(2)新增一个键值(maybe),计算香农熵,观察其变化(熵越高,则混合的数据也越多);

593
来自专栏一心无二用,本人只专注于基础图像算法的实现与优化。

基于模糊集理论的一种图像二值化算法的原理、实现效果及代码

  这是篇很古老的论文中的算法,发表与1994年,是清华大学黄良凯(Liang-kai Huang) 所写,因此国外一些论文里和代码里称之为Huang's fu...

22210
来自专栏BestSDK

10行代码告诉你,为什么说Python数据可视化是一件艺术品

1. 画散点图 画散点图用plt.scatter(x,y)。画连续曲线在下一个例子中可以看到,用到了plt.plot(x,y)。 plt.xticks(loc,...

4036

扫描关注云+社区