ToB企服应用市场:ToB评测及商务社交产业平台

标题: 使用Go复刻skiplist核心功能 [打印本页]

---

作者: 万万哇    时间: 5 天前
标题: 使用Go复刻skiplist核心功能
0、引言

正好做LC逐日一题要求实现一个跳表，于是学习了redis的扩展skiplist，并使用Go进行复刻学习。学习参考了文章：Redis内部数据布局详解(6)——skiplist - 铁蕾的个人博客
因为作者本领有限，本文只是对跳表的核心功能：创建节点与跳表、插入节点、删除节点、获取节点rank、根据rank获取节点、获取分数区间的ele集合进行复刻，其余的需要自己去实现。
1、跳表核心布局

源码的数据布局定义如下：

1. #define ZSKIPLIST_MAXLEVEL 32
2. #define ZSKIPLIST_P 0.25
4. /* ZSETs use a specialized version of Skiplists */
5. typedef struct zskiplistNode {
6.     sds ele;
7.     double score;
8.     struct zskiplistNode *backward;
9.     struct zskiplistLevel {
10.         struct zskiplistNode *forward;
11.         unsigned long span;
12.     } level[];
13. } zskiplistNode;
15. typedef struct zskiplist {
16.     struct zskiplistNode *header, *tail;
17.     unsigned long length;
18.     int level;
19. } zskiplist;

复制代码

• 定义了两个常量，一个是跳表的最大层数ZSKIPLIST_MAXLEVEL，一个是当前节点含有i+1层的概率ZSKIPLIST_P
  
• 跳表节点zskiplistNode：
  
  
  
  • ele，为string范例，存放的是节点的数据
    
  • score，存放数据对应的值
    
  • backward指向前一个跳表节点，只存在第一层链接中
    
  • level存放多层指向下一个节点的指针forawrd，同时含有一个span用于表示当前指针超过了多少个节点，用于实现通过排名查询。注意，span是表示当前层，从header到当前节点跨过的指针数，它不包罗指针的起始节点，但是包罗终点节点。
    
  
  
• 跳表本身zskiplist：
  
  
  
  • header和tail，指向跳表首尾的指针
    
  • length跳表总节点数
    
  • level跳表当前的层数
    
  
  

复刻：

1. package goskiplist
3. const (
4.         SKIPLIST_MAXLEVEL = 32
5.         SKIPLIST_P        = 0.25
6. )
8. type GskiplistLevel struct {
9.         forward *GskiplistNode
10.         span    uint64
11. }
12. type GskiplistNode struct {
13.         ele      string
14.         score    float64
15.         backward *GskiplistNode
16.         level    []GskiplistLevel
17. }
18. type Gskiplist struct {
19.         header *GskiplistNode
20.         tail   *GskiplistNode
21.         length uint64
22.         level int
23. }

复制代码

2、创建跳表节点与跳表

创建跳表节点源码：

1. zskiplistNode *zslCreateNode(int level, double score, sds ele) {
2.     zskiplistNode *zn =
3.         zmalloc(sizeof(*zn)+level*sizeof(struct zskiplistLevel));
4.     zn->score = score;
5.     zn->ele = ele;
6.     return zn;
7. }

复制代码

复刻：

1. func createNode(level int, score float64, ele string) *GskiplistNode{
2.         node := &GskiplistNode{
3.                 ele:      ele,
4.                 score:    score,
5.                 level:    make([]GskiplistLevel, level),
6.                 backward: nil,
7.         }
8.         return node
9. }

复制代码

创建跳表源码：

1. /* Create a new skiplist. */
2. zskiplist *zslCreate(void) {
3.     int j;
4.     zskiplist *zsl;
6.     zsl = zmalloc(sizeof(*zsl));
7.     zsl->level = 1;
8.     zsl->length = 0;
9.     zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL,0,NULL);
10.     for (j = 0; j < ZSKIPLIST_MAXLEVEL; j++) {
11.         zsl->header->level[j].forward = NULL;
12.         zsl->header->level[j].span = 0;
13.     }
14.     zsl->header->backward = NULL;
15.     zsl->tail = NULL;
16.     return zsl;
17. }

复制代码

初始化设置了跳表的层数为1、节点数为0、初始化头节点指针，分配内存。注意，头节点并不计算在length中。
颠末初始化，创建的跳表如下：

3、向跳表插入节点

源码：

1. zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) {
2.     zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
3.     unsigned long rank[ZSKIPLIST_MAXLEVEL];
4.     int i, level;
6.     serverAssert(!isnan(score));
7.     x = zsl->header;
8.     for (i = zsl->level-1; i >= 0; i--) {
9.         /* store rank that is crossed to reach the insert position */
10.         rank[i] = i == (zsl->level-1) ? 0 : rank[i+1];
11.         while (x->level[i].forward &&
12.                 (x->level[i].forward->score < score ||
13.                     (x->level[i].forward->score == score &&
14.                     sdscmp(x->level[i].forward->ele,ele) < 0)))
15.         {
16.             rank[i] += x->level[i].span;
17.             x = x->level[i].forward;
18.         }
19.         update[i] = x;
20.     }
21.     /* we assume the element is not already inside, since we allow duplicated
22.      * scores, reinserting the same element should never happen since the
23.      * caller of zslInsert() should test in the hash table if the element is
24.      * already inside or not. */
25.     level = zslRandomLevel();
26.     if (level > zsl->level) {
27.         for (i = zsl->level; i < level; i++) {
28.             rank[i] = 0;
29.             update[i] = zsl->header;
30.             update[i]->level[i].span = zsl->length;
31.         }
32.         zsl->level = level;
33.     }
34.     x = zslCreateNode(level,score,ele);
35.     for (i = 0; i < level; i++) {
36.         x->level[i].forward = update[i]->level[i].forward;
37.         update[i]->level[i].forward = x;
39.         /* update span covered by update[i] as x is inserted here */
40.         x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);
41.         update[i]->level[i].span = (rank[0] - rank[i]) + 1;
42.     }
44.     /* increment span for untouched levels */
45.     for (i = level; i < zsl->level; i++) {
46.         update[i]->level[i].span++;
47.     }
49.     x->backward = (update[0] == zsl->header) ? NULL : update[0];
50.     if (x->level[0].forward)
51.         x->level[0].forward->backward = x;
52.     else
53.         zsl->tail = x;
54.     zsl->length++;
55.     return x;
56. }

复制代码

zslInsert重要实现了向跳表中插入一个节点，节点的值为ele，分数为score。
解析：
（1）创建数组与断言检查

1. zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
2. unsigned long rank[ZSKIPLIST_MAXLEVEL];
3. int i, level;
4. serverAssert(!isnan(score));
5. x = zsl->header;

复制代码

• *update[]用于记录每一层插入的位置，update表示节点在第i层，应该插入在update节点之后。
  
• rank[]用于记录每一层的跨度，rank表示从第i层，跳到update节点的跨度。使用了前缀和的头脑。
  
• *x用于节点的遍历
  
• serverAssert用于判断数值是否非常
  

（2）查找插入位置

1. for (i = zsl->level-1; i >= 0; i--) {
2.         /* store rank that is crossed to reach the insert position */
3.         rank[i] = i == (zsl->level-1) ? 0 : rank[i+1];
4.         while (x->level[i].forward &&
5.                 (x->level[i].forward->score < score ||
6.                     (x->level[i].forward->score == score &&
7.                     sdscmp(x->level[i].forward->ele,ele) < 0)))
8.         {
9.             rank[i] += x->level[i].span;
10.             x = x->level[i].forward;
11.         }
12.         update[i] = x;
13.     }

复制代码

i从当前跳表的最高层向下遍历。在每一次遍历中：
<ul>rank初始赋值上一层的结果，若为最高层则赋值0
若当<strong>前层的当前节点存在下一节点，并且分数 zsl->level) {        for (i = zsl->level; i < level; i++) {            rank = 0;            update = zsl->header;            update->level.span = zsl->length;        }        zsl->level = level;    }[/code]使用zslRandomLevel函数设定新节点的最高层数。假如这个最高层数大于目前跳表的层数，那么就需要设定新高层的rank和update。
zslRandomLevel的实现如下：

1. level = zslRandomLevel();
2.     if (level > zsl->level) {
3.         for (i = zsl->level; i < level; i++) {
4.             rank[i] = 0;
5.             update[i] = zsl->header;
6.             update[i]->level[i].span = zsl->length;
7.         }
8.         zsl->level = level;
9.     }

复制代码

调整每一层的要插入的位置的前一个节点的指针指向，并且更新span。
假设在第i层，我们称update为pre，未更新前pre的下一个节点未next，那么因为要在pre和next之间插入新的节点，更新pre的span为pre到next的距离-cur到next的距离。更新cur的span为cur到next的距离。
第二个循环是为了更新当前节点的更高层未更新节点的span值。
颠末这一次调整，如图：

这里我画图用于形象的表示span的计算过程，它采用了前缀和的方式：

（5）更新新节点的前指针

1. int zslRandomLevel(void) {
2.     static const int threshold = ZSKIPLIST_P*RAND_MAX;
3.     int level = 1;
4.     while (random() < threshold)
5.         level += 1;
6.     return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
7. }

复制代码

假如update[0]不是头节点，那么它就是x的前一个节点。假如x的后节点存在，则更新x的后节点的前指针指向x，否则x是末端节点，让tail指向它。
复刻Go源码：

1. x = zslCreateNode(level,score,ele);
2.     for (i = 0; i < level; i++) {
3.         x->level[i].forward = update[i]->level[i].forward;
4.         update[i]->level[i].forward = x;
6.         /* update span covered by update[i] as x is inserted here */
7.         x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);
8.         update[i]->level[i].span = (rank[0] - rank[i]) + 1;
9.     }
10. /* increment span for untouched levels */
11.     for (i = level; i < zsl->level; i++) {
12.         update[i]->level[i].span++;
13.     }

复制代码

4、删除跳表节点

1. x->backward = (update[0] == zsl->header) ? NULL : update[0];
2.     if (x->level[0].forward)
3.         x->level[0].forward->backward = x;
4.     else
5.         zsl->tail = x;
6.     zsl->length++;
7.     return x;

复制代码

先来看zslDelete：它是删除节点的最上层，update的更新方法与插入同等。接着就是删除score和ele相同的节点，其中node参数用于提供保存删除节点的作用。在Go语言的复刻中，我们可以直接返回node和是否删除成功。
再看zslDeleteNode，它是删除节点的下游详细实现，详细细节如下：

• 逐层删除x，假如当前层有x，则需要将前一个节点的后指针指向x的后指针，然后更新前一个节点的span；否则只用更新span
  
• 假如x的后节点存在，则更新后节点的backward指针，否则修改跳表的tail。
  
• 假如存在高层，在删除x后为空层，要修改跳表的层数。
  
• 减去一个length
  

Go复刻如下：

1. // 向跳表插入一个节点，同时返回插入好的节点。
2. // ele不能为空串，否则返回nil。
3. func (this *Gskiplist) Insert(score float64, ele string) *GskiplistNode {
4.         if ele == "" {
5.                 return nil
6.         }
7.         update := make([]*GskiplistNode, SKIPLIST_MAXLEVEL)
8.         rank := make([]uint64, SKIPLIST_MAXLEVEL)
9.         var x *GskiplistNode
11.         x = this.header
12.         //更新update以及rank
13.         for i := this.level - 1; i >= 0; i-- {
14.                 rank[i] = 0
15.                 if i != this.level-1 {
16.                         rank[i] = rank[i+1]
17.                 }
18.                 for x.level[i].forward != nil &&
19.                         (x.level[i].forward.score < score ||
20.                                 (x.level[i].forward.score == score && x.level[i].forward.ele < ele)) {
21.                         rank[i] += x.level[i].span
22.                         x = x.level[i].forward
23.                 }
24.                 update[i] = x
25.         }
26.         level := this.randomLevel()
27.         //更新最大层数
28.         if level > this.level {
29.                 for i := this.level; i < level; i++ {
30.                         rank[i] = 0
31.                         update[i] = this.header
32.                         update[i].level[i].span = this.length
33.                 }
34.                 this.level = level
35.         }
36.         x = createNode(level, score, ele)
38.         //插入操作
39.         for i := 0; i < level; i++ {
40.                 x.level[i].forward = update[i].level[i].forward
41.                 update[i].level[i].forward = x
42.                 //更新x和前一个节点的span
43.                 x.level[i].span = update[i].level[i].span - (rank[0] - rank[i])
44.                 update[i].level[i].span = (rank[0] - rank[i]) + 1
45.         }
47.         //更新更高层
48.         for i := level; i < this.level; i++ {
49.                 update[i].level[i].span++
50.         }
52.         //更新前节点指针指向
53.         x.backward = nil
54.         if update[0] != this.header {
55.                 x.backward = update[0]
56.         }
57.         if x.level[0].forward != nil {
58.                 x.level[0].forward.backward = x
59.         } else {
60.                 this.tail = x
61.         }
62.         this.length++
63.         return x
64. }

复制代码

5、获取节点的rank

1. void zslDeleteNode(zskiplist *zsl, zskiplistNode *x, zskiplistNode **update) {
2.     int i;
3.     for (i = 0; i < zsl->level; i++) {
4.         if (update[i]->level[i].forward == x) {
5.             update[i]->level[i].span += x->level[i].span - 1;
6.             update[i]->level[i].forward = x->level[i].forward;
7.         } else {
8.             update[i]->level[i].span -= 1;
9.         }
10.     }
11.     if (x->level[0].forward) {
12.         x->level[0].forward->backward = x->backward;
13.     } else {
14.         zsl->tail = x->backward;
15.     }
16.     while(zsl->level > 1 && zsl->header->level[zsl->level-1].forward == NULL)
17.         zsl->level--;
18.     zsl->length--;
19. }
21. int zslDelete(zskiplist *zsl, double score, sds ele, zskiplistNode **node) {
22.     zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
23.     int i;
25.     x = zsl->header;
26.     for (i = zsl->level-1; i >= 0; i--) {
27.         while (x->level[i].forward &&
28.                 (x->level[i].forward->score < score ||
29.                     (x->level[i].forward->score == score &&
30.                      sdscmp(x->level[i].forward->ele,ele) < 0)))
31.         {
32.             x = x->level[i].forward;
33.         }
34.         update[i] = x;
35.     }
36.     /* We may have multiple elements with the same score, what we need
37.      * is to find the element with both the right score and object. */
38.     x = x->level[0].forward;
39.     if (x && score == x->score && sdscmp(x->ele,ele) == 0) {
40.         zslDeleteNode(zsl, x, update);
41.         if (!node)
42.             zslFreeNode(x);
43.         else
44.             *node = x;
45.         return 1;
46.     }
47.     return 0; /* not found */
48. }

复制代码

从高层逐个寻找，找到即返回。
6、根据排名获取节点

1. //删除节点，返回这个节点以及是否成功
2. func (this *Gskiplist) Delete(score float64, ele string) (*GskiplistNode, bool) {
3.         update := make([]*GskiplistNode, SKIPLIST_MAXLEVEL)
4.         var x *GskiplistNode
6.         x = this.header
7.         for i := this.level - 1; i >= 0; i-- {
8.                 for x.level[i].forward != nil &&
9.                         (x.level[i].forward.score < score ||
10.                                 (x.level[i].forward.score == score && x.level[i].forward.ele < ele)) {
11.                         x = x.level[i].forward
12.                 }
13.                 update[i] = x
14.         }
16.         x = x.level[0].forward
17.         //从底层删除
18.         if x != nil && x.score == score && x.ele == ele {
19.                 this.deleteNode(x, update)
20.                 return x, true
21.         }
22.         //未找到对应节点
23.         return nil, false
24. }
26. func (this *Gskiplist) deleteNode(x *GskiplistNode, update []*GskiplistNode) {
27.         for i := 0; i < this.level; i++ {
28.                 if update[i].level[i].forward == x {
29.                         //在这一层，存在x
30.                         update[i].level[i].span += x.level[i].span - 1
31.                         update[i].level[i].forward = x.level[i].forward
32.                 } else {
33.                         //不存在则只更新span
34.                         update[i].level[i].span--
35.                 }
36.         }
37.         if x.level[0].forward != nil {
38.                 x.level[0].forward.backward = x.backward
39.         } else {
40.                 this.tail = x.backward
41.         }
43.         //若x独占高层，需要逐个清除
44.         for this.level > 1 && this.header.level[this.level-1].forward == nil {
45.                 this.level--
46.         }
47.         this.length--
48. }

复制代码

Go复刻：
[code]// 根据排名获取节点func (this *Gskiplist) GetElementByRank(rank uint64) *GskiplistNode {        return this.getElementByRankFromNode(this.header, this.level-1, rank)}func (this *Gskiplist) getElementByRankFromNode(startNode *GskiplistNode, startLevel int, rank uint64) *GskiplistNode {        x := startNode        var traversed uint64        for i := startLevel; i >= 0; i-- {                for x.level.forward != nil && traversed+x.level.span = 0; i-- {                for x.level.forward != nil && x.level.forward.score < low {                        x = x.level.forward                }        }        x = x.level[0].forward        for x != nil && x.score

---

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)

Powered by Discuz! X3.4