Shulou(Shulou.com)06/02 Report--

This article introduces the relevant knowledge of "how to use jump tables to achieve SortedSet in Golang". In the operation of actual cases, many people will encounter such a dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

Structure definition

The simplest data structure to implement the ZRange command is an ordered linked list:

Implementing ZRange key start end commands on ordered linked lists requires end queries, that is, the time complexity is O (n).

The optimization idea of the jump table is to add the upper linked list, and some nodes will be skipped in the upper linked list. As shown in the figure:

In the two-tier jump table, the time complexity of the search is reduced to O (n / 2). And so on, in a hopping table with log2 (n) layer, the time complexity of searching for elements is O (log n).

Now that you understand the data structure, you can define the relevant types:

/ / external element abstraction type Element struct {Member string Score float64} type Node struct {Element / / element name and score backward * Node / / backward pointer level [] * Level / / forward pointer Level [0] is the definition of the abstract type Level struct {forward * Node / / pointing to the next node in the same layer span int64 / to the number of nodes skipped by forward} / / the definition of the type skiplist struct {header * Node tail * Node length int64 level int16} for each layer in the lowest layer} / /

Show it with a picture:

Find Node

With the logic of finding nodes described above, it is not difficult to implement, take the core logic of RangeByRank as an example:

/ / find the node ranked as rank. Rank starts from 1 func (skiplist * skiplist) getByRank (rank int64) * Node {var I int64 = 0n: = skiplist.header / / query for level: = skiplist.level-1; level > = 0 from the top level Level-- {/ / search forward from the current layer / / if the next node of the current layer has exceeded the target (I + n.level] .span > rank), end the current level search and go to the next level for n.level] .forward! = nil & & (i+ n.level.span) = 0 Level-- {/ / if the forward node is not in range, continue to move forward (forward) / / if the forward node has entered the range, when level > 0, the forward node cannot be guaranteed to be * the first * node in the min range. Therefore, you need to go to the next level to find for n.level [level] .forward! = nil & &! min.less (n.level [level] .progresd.Score) {n = n.level [level] .forward}} / / level=0 when exiting from the outer loop. N.level [0] .forward must be the first node in the range of min n = n.level [0] .forward if! max.greater (n.Score) {return nil} return n} insert node

There are many operations to insert nodes, which are explained in the form of comments:

Func (skiplist * skiplist) insert (member string, score float64) * Node {/ / find the pioneer node of the new node Their forward will point to the new node / / because each layer has a forward pointer, so each layer will correspond to a pioneer node / / find these pioneer nodes and save them in the update array update: = make ([] * Node, maxLevel) rank: = make ([] int64, maxLevel) / / save the ranking of the pioneer nodes for each layer, which is used to calculate span node: = skiplist.header for I: = skiplist.level-1 I > = 0 IMel-{/ / search down from the top / / initialize rank if i = = skiplist.level-1 {rank [I] = 0} else {rank [I] = rank [I + 1]} if node.level [I]! = nil {/ / traversal search for node.level [ I] .forward! = nil & & (node.level [I] .accepd.Score

< score || (node.level[i].forward.Score == score && node.level[i].forward.Member < member)) { // same score, different key rank[i] += node.level[i].span node = node.level[i].forward } } update[i] = node } level := randomLevel() // 随机决定新节点的层数 // 可能需要创建新的层 if level >

Skiplist.level {for I: = skiplist.level; I

< level; i++ { rank[i] = 0 update[i] = skiplist.header update[i].level[i].span = skiplist.length } skiplist.level = level } // 创建新节点并插入跳表 node = makeNode(level, score, member) for i := int16(0); i < level; i++ { // 新节点的 forward 指向先驱节点的 forward node.level[i].forward = update[i].level[i].forward // 先驱节点的 forward 指向新节点 update[i].level[i].forward = node // 计算先驱节点和新节点的 span node.level[i].span = update[i].level[i].span - (rank[0] - rank[i]) update[i].level[i].span = (rank[0] - rank[i]) + 1 } // 新节点可能不会包含所有层 // 对于没有层，先驱节点的 span 会加1 (后面插入了新节点导致span+1) for i := level; i < skiplist.level; i++ { update[i].level[i].span++ } // 更新后向指针 if update[0] == skiplist.header { node.backward = nil } else { node.backward = update[0] } if node.level[0].forward != nil { node.level[0].forward.backward = node } else { skiplist.tail = node } skiplist.length++ return node} randomLevel 用于随机决定新节点包含的层数，随机结果出现2的概率是出现1的25%， 出现3的概率是出现2的25%: func randomLevel() int16 { level := int16(1) for float32(rand.Int31()&0xFFFF) < (0.25 * 0xFFFF) { level++ } if level < maxLevel { return level } return maxLevel}删除节点 删除节点的思路与插入节点基本一致: // 删除操作可能一次删除多个节点func (skiplist *skiplist) RemoveRangeByRank(start int64, stop int64)(removed []*Element) { var i int64 = 0 // 当前指针的排名 update := make([]*Node, maxLevel) removed = make([]*Element, 0) // 从顶层向下寻找目标的先驱节点 node := skiplist.header for level := skiplist.level - 1; level >

= 0; level-- {for node.level] .forward! = nil & & (I + node.level] .span)

< start { i += node.level[level].span node = node.level[level].forward } update[level] = node } i++ node = node.level[0].forward // node 是目标范围内第一个节点 // 删除范围内的所有节点 for node != nil && i < stop { next := node.level[0].forward removedElement := node.Element removed = append(removed, &removedElement) skiplist.removeNode(node, update) node = next i++ } return removed} 接下来分析一下执行具体节点删除操作的removeNode函数: // 传入目标节点和删除后的先驱节点// 在批量删除时我们传入的 update 数组是相同的func (skiplist *skiplist) removeNode(node *Node, update []*Node) { for i := int16(0); i < skiplist.level; i++ { // 如果先驱节点的forward指针指向了目标节点，则需要修改先驱的forward指针跳过要删除的目标节点 // 同时更新先驱的 span if update[i].level[i].forward == node { update[i].level[i].span += node.level[i].span - 1 update[i].level[i].forward = node.level[i].forward } else { update[i].level[i].span-- } } // 修改目标节点后继节点的backward指针 if node.level[0].forward != nil { node.level[0].forward.backward = node.backward } else { skiplist.tail = node.backward } // 必要时删除空白的层 for skiplist.level >

1 & & skiplist.header.level [skiplist.level-1] .forward = = nil {skiplist.level--} skiplist.length--} "how to use jump tables in Golang to achieve SortedSet" is introduced here, thank you for reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.