算法：跳跃表的实现 用python实现跳跃表 ``` 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层。层数越大的节点越少。具体上，可以这样实现： ``` 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] ``` 来自 大脸猫 写于 2017-12-06 17:34 -- 更新于2020-10-19 13:06 -- 0 条评论