用python实现了跳跃表，之前还写了一个有序的单向链表，我都插入了两万个数据，跳跃表是建立了两层索引，查找一个没有插入的数据，在自己的电脑上，跳跃表大概用了0.000016，单向链表大概是0.06左右
import random,datetime
import time
class Node(object):
def __init__(self, data):
self.data = data
self.right = None
self.down = None
class SkipList(object):
def __init__(self):
"""
header 数据层head
index_first_header: 建立索引第一层的head
temporary_header: 临时的用于查找从那个地方插入数据
first_header: 第一个索引，用于查找数据
"""
self.header = None
self.index_first_header = None
self.temporary_header = None
self.first_header = None
# level 为索引高度
self.level = 2
self.init_skip_list()
def init_skip_list(self):
"""初始化时先初始化好跳表最左侧数据"""
index_list = self.set_index(None)
node = self.set_node(None)
for i in range(self.level):
if i != len(index_list)-1:
index_list[i].down = index_list[i+1]
index_list[-1].down = node
node.right = self.header
self.header = index_list[0]
self.index_first_header = index_list[0]
self.first_header = index_list[0]
def random_level(self):
"""随机建立索引算法"""
return_num = -1
random_list = []
denominator = 2 ** (self.level+1)
for i in range(denominator):
random_list.append(i+1)
while True:
random_num = random.randint(1, denominator)
if random_num in random_list[0:int(len(random_list)/2)]:
return_num = 0
elif random_num in random_list[int(len(random_list)/2):int(len(random_list)/2)+int(len(random_list)/4)]:
return_num = 1
elif random_num in random_list[int(len(random_list)/2)+int(len(random_list)/4):int(len(random_list)/2)+int(len(random_list)/4)+int(len(random_list)/8)]:
return_num = 2
if return_num != -1:
return return_num
def search_node(self, data):
"""查找数据"""
# 验证数据是否为空
if self.is_data_null(data):
return
head_node = self.first_header
while True:
if head_node.right and head_node.right.data <= data:
head_node = head_node.right
if head_node.data == data:
return True
elif head_node.down:
head_node = head_node.down
else:
break
return False
def add_node(self, data):
"""添加数据"""
# 验证数据是否为空
if self.is_data_null(data):
return
node = self.header
# 如果是第一次创建，则不用随机创建索引，直接加入数据层
if node.right is None:
set_node = self.set_node(data)
for i in range(self.level):
node = node.down
node.right = set_node
self.header = node
return
right_node_list = []
left_node_list = []
index_level = self.random_level()
index_list = self.set_index(data, mold=index_level)
# 开始查找数据并插入数据
index_first_header_node = self.index_first_header
remain_level = self.level - len(index_list)
for i in range(remain_level):
# 此时的index_first_header_node为需要创建索引的node
index_first_header_node = index_first_header_node.down
# 此时的index_first_header_node为需要创建索引的node
self.temporary_header = index_first_header_node
for i in range(index_level):
if i != len(index_list) - 1:
index_list[i].down = index_list[i+1]
set_node = self.set_node(data)
if len(index_list) != 0:
index_list[-1].down = set_node
index_list.append(set_node)
data_equal = 1
for set_node in index_list:
data_node = self.temporary_header
if data_equal == 2:
break
while True:
if data_node.right is not None:
if data_node.right.data < data:
data_node = data_node.right
if data_node.right is None:
right_node_list.append(None)
left_node_list.append(data_node)
self.temporary_header = self.temporary_header.down
break
elif data_node.right.data == data:
data_equal = 2
index_level = -1
break
else:
right_node_list.append(data_node.right)
left_node_list.append(data_node)
self.temporary_header = self.temporary_header.down
break
else:
right_node_list.append(None)
left_node_list.append(data_node)
self.temporary_header = self.temporary_header.down
break
for i in range(index_level+1):
new_node = index_list[i]
left_node = left_node_list[i]
right_node = right_node_list[i]
left_node.right = new_node
new_node.right = right_node
if data == 5:
a = self.first_header
s = 1
print("第一层")
while a.right:
a = a.right
s += 1
# print(a.data)
print("第一层的个数是:{}".format(s))
a = self.first_header.down
print("第二层")
ss = 1
while a.right:
a = a.right
ss += 1
# print(a.data)
print("第二层的个数是:{}".format(ss))
a = self.first_header.down.down
print("第三层")
sss = 1
while a.right:
a = a.right
sss += 1
# print(a.data)
print("第三层个数是:{}".format(sss))
def is_data_null(self, data):
"""验证数据是否为空"""
if data:
return False
else:
return True
def set_node(self, data):
"""创建数据节点"""
return Node(data)
def set_index(self, data, mold=-1):
"""创建索引节点"""
index_list = []
# 初始化索引
if mold == -1:
for i in range(self.level):
index_list.append(Node(data))
# 随机算法索引
else:
for i in range(mold):
index_list.append(Node(data))
return index_list
if __name__ == '__main__':
skip = SkipList()
for i in range(20000):
num = random.randint(7, 10000)
skip.add_node(num)
skip.add_node(5)
time_1 = datetime.datetime.now()
is_exist = skip.search_node(1)
time_2 = datetime.datetime.now()
print(time_2-time_1)
print(is_exist)
