折腾redis的sorted set数据结构Skip List跳跃表

我旁边的同时一直在捣鼓redis的分页功能,详细的分析了list和sorted set的两个结构.   我自己也对sorted set的数据结构很是感兴趣…  我这边的有个微信抓取的任务就是用python rq做的,里面的选用的redis数据类型就是sorted set…   这里不是重点,有时间专门写一篇关于redis实现时序任务队列的方式。


xiaorui.cc

xiaorui.cc

xiaorui.cc

开始先是介绍skip list :


Skip List是一种随机化的数据结构,基于并联的链表,其效率可比拟于二叉查找树(对于大多数操作需要O(log n)平均时间)。基本上,跳跃列表是对有序的链表增加上附加的前进链接,增加是以随机化的方式进行的,所以在列表中的查找可以快速的跳过部分列表(因此得名)。所有操作都以对数随机化的时间进行。Skip List可以很好解决有序链表查找特定值的困难。

Skip List定义
一个skip list 跳表,应该具有以下特征:
  一个跳表应该有几个层(level)组成;
  跳表的第一层包含所有的元素;
  每一层都是一个有序的链表;
  如果元素x出现在第i层,则所有比i小的层都包含x;
  第i层的元素通过一个down指针指向下一层拥有相同值的元素;
  在每一层中,-1和1两个元素都出现(分别表示INT_MIN和INT_MAX);
  Top指针指向最高层的第一个元素。

大家看下面的图片,一共构造了三层,根据上面的一些个特性,估计你也能理解一二了。   举个例子,你如果想查找14,那么先从第三层开始搞起,因为是有序的,所以14可以确定是在第二层的7和21之间,然后呢,再到第三层就能找到了。 他的一些算法是含有一些随机性的。 


那么我们再来查找117和118 

例子:查找元素 117
(1) 比较 21, 比 21 大,往后面找
(2) 比较 37,   比 37大,比链表最大值小,从 37 的下面一层开始找
(3) 比较 71,  比 71 大,比链表最大值小,从 71 的下面一层开始找
(4) 比较 85, 比 85 大,从后面找
(5) 比较 117, 等于 117, 找到了节点。

下面是我在wiki找到的一个流程动画,方便大家理解

跳表的插入方式

有人也用python实现了skip list的功能,有兴趣的朋友可以看看。   代码还算干练,对于理解skip list 也是很有帮助的。 

from math import log
from random import random, seed

class Node( object ):
    def __init__( self,
                  value = None, 
                  next = [] ):
        self.value = value
        self.next = next

class End( object ):
    def __cmp__( self, other ):
        return 1 # always greater than any other object

END = Node( End(), [] )

class SkipList:
    def __init__( self, expected_size = 100, p = 0.5 ):
        self.size = 0
        self.maxlevels = int( log(expected_size, 2) + 1 )
        self.head = Node( 'HEAD', [END] * self.maxlevels )
        self.p = p

    def random_level( self ):
        lev = 1
        while ((random() < self.p) and (lev < self.maxlevels)):
            lev = lev + 1
        return lev

    def insert( self, value ):
        saveprev = [None] * self.maxlevels
        node = self.head
        for lev in reversed( range(self.maxlevels) ):
            while (node.next[lev].value <= value):
                node = node.next[lev]
            saveprev[lev] = node
        new = Node( value = value,
                    next = [ None ] * self.random_level() )
        for lev in range( len(new.next) ):
            # saveprev[lev] points to new[lev]
            tmp = saveprev[lev].next[lev]
            saveprev[lev].next[lev] = new
            new.next[lev] = tmp
        self.size = self.size + 1

    def delete( self, value ):
        node = self.head
        saveprev = [None] * self.maxlevels
        for lev in reversed( range(self.maxlevels) ):
            while (node.next[lev].value < value):
                node = node.next[lev]
            saveprev[lev] = node
        node = saveprev[0].next[0]
        if node.value == value:
            # saveprev[0] points to the node to be deleted
            for lev in range( self.maxlevels ):
                if saveprev[lev].next[lev] != node:
                    break
                saveprev[lev].next[lev] = node.next[lev]
                node.next[lev] = None
            self.size = self.size - 1

    def printme( self ):
        print "Size = ", self.size
        print "Maxlevels = ", self.maxlevels
        node = self.head
        node = node.next[0]
        while (node != END):
            print "->", node.value,
            node = node.next[0]
        print

if __name__ == "__main__":
    # Simple test
    # TODO: This should be put in a test suite.
    from random import randint
    seed( 8 )
    l = [ randint(0, 90000) for x in xrange(800000) ]
    seed( 31 )
    print "Running myskiplist test:"
    mylist = SkipList( expected_size = 800000, p = 0.25 )
    for x in l:
        mylist.insert( x )
    print "Initial list:"
    print "Size:", mylist.size
    # mylist.printme()
    # delete some keys
    d = [ randint(0, 90000) for x in xrange(2000000) ]
    # d = [510, 507]
    for x in d:
        # print "Deleting key:", x
        mylist.delete(x)
    print "After deletes:"
    print "Size:", mylist.size
    # mylist.printme()
    print "Done."


大家觉得文章对你有些作用! 如果想赏钱,可以用微信扫描下面的二维码,感谢!
另外再次标注博客原地址  xiaorui.cc

2 Responses

  1. 王超 2015年4月28日 / 上午8:14

    这个不错!

  2. udc-7301970 2015年3月28日 / 上午7:40

    学习了

发表评论

邮箱地址不会被公开。 必填项已用*标注