大猪 & 大兔

用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]