python实现跳表SkipList的示例代码

时间:2022-11-06 14:25:58

跳表

跳表,又叫做跳跃表、跳跃列表,在有序链表的基础上增加了“跳跃”的功能,由william pugh于1990年发布,设计的初衷是为了取代平衡树(比如红黑树)。
redis、leveldb 都是著名的 key-value 数据库,而redis中 的 sortedset、leveldb 中的 memtable 都用到了跳表。
对比平衡树,跳表的实现和维护会更加简单,跳表的搜索、删除、添加的平均时间复杂度是 o(logn)。
跳表的结构如图所示:

python实现跳表SkipList的示例代码

可以发现,对于一个节点node,其含有多个next指针,不同索引的next分别代表不同层次的下一个节点,下次是节点类node的python定义:

?
1
2
3
4
5
6
7
8
9
10
11
12
class node():
     def __init__(self,key,value,level):
         '''
         :param level:每个node对应的nexts层数不同
         '''
         self.key=key
         self.value=value
         self.nexts=[none]*level#节点类型next指针,初始值为空
 
     def __str__(self):
         #return "[key:"+str(self.key)+", value:"+str(self.value)+" len:"+str(len(self.nexts))+"]"
         return "["+str(self.key)+","+str(self.value)+","+str(len(self.nexts))+"]"

关于添加、删除、查找见一下完整代码:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
'''
跳表 skip list ,其初衷是为了替代红黑树
'''
import random
 
import mkl_random
import time
 
class skiplist():
    def __init__(self):
        #头节点不存储任何数据
        self.max_level = 32  # 最大level层数
        self.__first=skiplist.node(none, none, self.max_level)#头节点
        self.__level=0#实际的level层数
        self.__size=0#jiedian个数
        self.__p=0.25#用于生成添加节点时的随机level
        return
 
    class node():
        def __init__(self,key,value,level):
            '''
            :param level:每个node对应的nexts层数不同
            '''
            self.key=key
            self.value=value
            self.nexts=[none]*level
 
        def __str__(self):
            #return "[key:"+str(self.key)+", value:"+str(self.value)+" len:"+str(len(self.nexts))+"]"
            return "["+str(self.key)+","+str(self.value)+","+str(len(self.nexts))+"]"
 
    def get(self,key):
        '''
        :param key:
        :return: key对应的value
        '''
        self.keycheck(key)
        node=self.__first
        for level in range(self.__level - 1,-1,-1):
            #在该层查找,key大于节点的key向前查找
            while node.nexts[level] and node.nexts[level].key<key:
                node=node.nexts[level]
            if node.nexts[level] and node.nexts[level].key==key:#相等则找到,否则向下寻找
                return node.nexts[level].value
        return none
 
    def put(self,key,value):
        '''
        return:原来的value,原来不存在key则为空
        '''
        self.keycheck(key)
        prev=[none]*self.__level
        node=self.__first
        for i in range(self.__level - 1, -1, -1):
            while node.nexts[i] and node.nexts[i].key<key:
                node=node.nexts[i]
            if node.nexts[i] and node.nexts[i].key==key:
                oldvalue=node.nexts[i].value
                node.nexts[i].value=value
                return oldvalue
            prev[i]=node#保存当前level小于key的node
 
        newlevel=self.randomlevel()
        newnode=skiplist.node(key,value,newlevel)
        for i in range(newlevel):
            if i<self.__level:
                newnode.nexts[i]=prev[i].nexts[i]
                prev[i].nexts[i]=newnode
            else:
                self.__first.nexts[i]=newnode
        self.__size+=1
        self.__level=max(self.__level, newlevel)
        return none
 
    def remove(self,key):
        '''
        :return: 节点对应的value值,不存在则返回none
        '''
        self.keycheck(key)
        prev=[none]*self.__level
        node=self.__first
        flag=false#该节点是否被查找到
        for i in range(self.__level - 1, -1, -1):
            while node.nexts[i] and node.nexts[i].key<key:
                node=node.nexts[i]
            if node.nexts[i].key==key:
                flag=true
            prev[i]=node
        if not flag:
            return none
        removednode=node.nexts[0]#需要被删除的节点
        for i in range(len(removednode.nexts)):#该nexts一定小于等于prev的长度
            prev[i].next[i]=removednode.nexts[i]
        self.__size-=1
        newlevel=self.__level
        while newlevel>0 and not self.__first.nexts[newlevel - 1]:
            newlevel-=1
        self.__level=newlevel
        return removednode.value
 
    def keycheck(self, key):
        '''
        限制传入key不能为空
        '''
        if key!=0 and not key:
            raise attributeerror("key can not be none")
 
    def size(self):
        return self.__size
 
    def isempty(self):
        return self.__size == 0
 
    def randomlevel(self):#生成一个随机的层数
        level=1
        while mkl_random.rand()<self.__p and level<self.max_level:
            level+=1
        return level
 
    def __str__(self):
        result=""
        for i in range(self.__level - 1, -1, -1):
            result+=str(i)
            node = self.__first
            while node.nexts[i]:
                result+=str(node.nexts[i])
                node=node.nexts[i]
            result+='\n'
        print("level:"+str(self.__level))
        return result
 
    def showfirst(self):
        for item in self.__first.nexts:
            print(item,end=' ')
        print()
 
def timecalculate(container, size:int):
    begin=time.time()
    for i in range(size):
        if isinstance(container,dict):
            container[i]= i * 3
        else:
            container.put(i, i * 3)
    error_count = 0
    for i in range(size):
        if container.get(i) != i * 3:
            #print("wrong " + str(i) + ":" + str(skiplist.get(i)))
            error_count+=1
    end=time.time()
    print(type(container))
    print(f'error rate:{float(error_count) / size:0.5f}')
    print(f'time cost:{float(end-begin)*1000:0.3f} ms')
 
 
if __name__=='__main__':
    timecalculate({},1000000)
    timecalculate(skiplist(),10000)

到此这篇关于python实现跳表skiplist的文章就介绍到这了,更多相关python 跳表skiplist内容请搜索服务器之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持服务器之家!

原文链接:https://blog.csdn.net/Demon_LMMan/article/details/119064581