用python实现跳跃表
代码语言：javascript复制import random
class SkipList(object):
def __init__(self):
self.level = [None, None, None, None, None]
def insert(self, node):
pre_node = self._find_pre(node)
node.prev = pre_node
will_affect = []
temp_node = pre_node
while 1:
if len(temp_node.level) < len(node.level):
will_affect.append(temp_node)
temp_node = temp_node.prev
else:
will_affect.append(temp_node)
break
for affect_node in will_affect:
for k, p_node in enumerate(affect_node.level):
if p_node is None or p_node.score > node.score:
if k < len(node.level):
# 修改指针
node.level[k] = p_node
affect_node.level[k] = node
def _find_pre(self, node):
pre_node = self
while 1:
for i in range(len(pre_node.level)-1, -1, -1):
p_node = pre_node.level[i]
if p_node is None:
continue
elif p_node.score > node.score:
continue
elif p_node.score <= node.score:
pre_node = p_node
break
else:
return pre_node
def get_range(self, start_score, stop_score):
start_node = self._find_pre(SkipListNode('', start_score))
while 1:
if isinstance(start_node, SkipList):
start_node = start_node.level[0]
break
if isinstance(start_node.prev, SkipList):
break
if start_node.prev.score >= start_score:
start_node = start_node.prev
else:
break
result = []
while 1:
if start_node and start_score <= start_node.score <= stop_score:
result.append(start_node)
start_node = start_node.level[0]
else:
break
return result
class SkipListNode(object):
def __init__(self, key, score):
self.key = key
self.score = score
self.prev = None
self.level = []
for i in range(0, random.randint(1,5)):
self.level.append(None)
if __name__ == '__main__':
# test
skip_list = SkipList()
node = SkipListNode('helloworld1', 1)
skip_list.insert(node)
node = SkipListNode('helloworld31', 3)
skip_list.insert(node)
node = SkipListNode('helloworld2', 2)
skip_list.insert(node)
node = SkipListNode('helloworld32', 3)
skip_list.insert(node)
node = SkipListNode('helloworld33', 3)
skip_list.insert(node)
result = skip_list.get_range(3, 3)
assert len(result) == 3
for node in result:
print(node.key)
print(node.score)
assert node.score == 3
result = skip_list.get_range(1, 2)
assert len(result) == 2
for node in result:
print(node.key)
print(node.score)
assert node.score in [1,2]Level的随机生成
在跳跃表中，每个节点的level数随机按1-5生成并不是很好，可以引入一个算法。在redis中，每个节点的level有1-32层。层数越大的节点越少。具体上，可以这样实现：
代码语言：javascript复制import random
import math
def get_random(size):
# 产生[0-n)的随机数，数越大，则产生的概率越小
return size - int(math.sqrt(random.randint(0, size*size-1))) -1
count = [0]*32
for i in range(1000000):
rnd = get_random(32)
count[rnd] = 1
print(count)
100W 次结果：
[61411, 59880, 57719, 55929, 53847, 51683, 49576, 47808, 45463, 43657, 41902, 40120, 38288, 36274, 34416, 32375, 30376,28179, 26208, 24222, 22481, 20539, 18502, 16698, 14615, 12859, 10536, 8892, 6803, 4925, 2878, 939]
