基于天然概率的无需人为平衡的skiplist的美之展现-创新互联

任何事情都无法阻挡我对一种简单之美的由衷惊叹。
半夜思索,无法入眠,索性起床看会书,关于中东文明的,可是又看不进去,也许是潮热的原因 吧...还不如静下心来写一篇意识流文章,我指的是不用思考的那种,我已经被近东,中东的错综复杂的历史搞的有点烦了,那真是太难了。然而你能想象我指的 那个不用思考的东西是一个算法吗?算法不都是很难的吗?真的就是一个算法,也可以说是一个数据结构,这就是skiplist。
      可以从网上找到大量深入分析skiplist的资料,包括分析其时间复杂度,空间占用情况的。但是本文不,因为我不想在一个如此美好的早上就消耗脑细胞,也不能说是早上,此时凌晨3点整!!注意,我是不需要怎么睡觉还能保持精力的那种怪人。
      那就开始了。
       说到查找,首先能想到的几乎就是各种查找树,当然,实际上在实用主义看来用得比较多的还是HASH,查找树可能学院派更加青睐一些吧。至于HASH,它可 能受制于扩展性,需要不断的reHASH操作,然而对于动态节点,有一种一致性HASH可以参考,大量用于分布式环境,它完美解决了扩展性问题。当然它体 现了另一种动态美,以后如果哪天早上又打鸡血了,会写一篇分析一下的。提到HASH的不易扩展性以及reHASH操作,查找树事实上是可以无限扩展的,但 是在扩展过程中,会破坏树的平衡性,破坏了平衡性就会严重损耗查找树的查找性能,因此为了在扩展过程中保持平衡,需要一种人为的干预,这种干预就是所谓的 “平衡”操作。
      不管对于AVL树,2-3-4树,还是衍生出来的红黑树,都是以上所述的这类查找树的典型。如果说有一种数据结构,在扩展过程中可以自然而然地保持平衡性,根本无需人为干预,那该有多好。
       我是一个基因决定论的信徒,相信任何的爆发或者陨灭都是由原始基本基因决定的,当然这是蝴蝶效应的一种体现。我天然反对健身房减肥,因为我相信瘦的人是基 因决定的,怎么吃都不会胖,就好比掰手腕,很多人根本就没有练过,但是天然力气惊人,瞬间扳倒在健身房练了好几年的,这些人一旦离开了健身房,马上肌肉就 变成了消失了,脂肪越来越多...这种在健身房练就一身肌肉的,就好像AVL树,红黑树,需要花费成本不断地进行平衡斧正,而对于那种天然基因决定的拥有 完美曲线的人,就好比skiplist,快乐生活,自由成长。

成都创新互联公司专注于企业营销型网站、网站重做改版、宽城网站定制设计、自适应品牌网站建设、H5场景定制电子商务商城网站建设、集团公司官网建设、成都外贸网站建设、高端网站制作、响应式网页设计等建站业务,价格优惠性价比高,为宽城等各大城市提供网站开发制作服务。

skiplist简介

本文就不介绍了,不过当你baidu了之后,你几乎也就理解了skiplist的全部,也就无需再接着看下去了,因此更多的,本文属于我自己的记录随笔。

插入过程理解skiplist

下图展示了一个skiplist的插入构建过程:

基于天然概率的无需人为平衡的skiplist的美之展现

基于天然概率的无需人为平衡的skiplist的美之展现

skiplist查找示例

基于天然概率的无需人为平衡的skiplist的美之展现

skiplist的美之展现

在画图的过程中,我发现不经意间所有的话都表达在图示里面了,无需更多的言语,这难道就是简单之美吗?

基于天然概率的无需人为平衡的skiplist的美之展现

统计性能!统计性能!统计性能!统计性能!还是统计性能!

另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。


网页标题:基于天然概率的无需人为平衡的skiplist的美之展现-创新互联
网站URL:http://myzitong.com/article/ccscis.html