日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網(wǎng)站首頁 編程語言 正文

GO實現(xiàn)跳躍表的示例詳解_Golang

作者：Onemorelight95 ? 更新時間： 2023-01-18 編程語言

跳躍表介紹

跳躍表（skiplist）是一種有序的數(shù)據(jù)結(jié)構(gòu)，它通過建立多層"索引"，從而達到快速訪問節(jié)點的目的. 跳躍表支持平均O(logN)、最壞O(N)復雜度的節(jié)點查找，還可以通過順序性操作來批量處理節(jié)點。

下面是一個跳表結(jié)構(gòu)的示意圖，其實跳表就是一個二維鏈表，只有最底層的鏈表中存著數(shù)據(jù)，其他層都是在第一層基礎(chǔ)上建立的索引，越靠近上層，節(jié)點之間的跨度就越大，跳表的查詢范圍也越大。依靠著這些索引，跳表可以實現(xiàn)接近二分查找的查找效率。

跳躍表的實現(xiàn)

跳躍表的結(jié)構(gòu)

跳表的元素

// Element 是一個key-score對組
type Element struct {
	Member string
	// 跳躍表節(jié)點依照Score升序排序，若一樣，則按照Member的字典升序排序
	Score float64
}

跳表的層結(jié)構(gòu)

// Level 層
type Level struct {
	// 指向前面一個節(jié)點
	forward *node
	// 與前一個節(jié)點的跨度
	span int64
}

跳表的節(jié)點

跳表的一個節(jié)點有三個字段：元素、指向前一個節(jié)點的指針和建立在該節(jié)點之上的層級。

// node 跳躍表的一個節(jié)點
type node struct {
	Element
	// 回退指針
	backward *node
	// 每個節(jié)點有 1~maxLevel 個層級
	level []*Level
}

跳表的表頭結(jié)構(gòu)

// skiplist 跳表結(jié)構(gòu)
type skiplist struct {
	// 指向表頭節(jié)點
	header *node
	// 指向表尾節(jié)點
	tail *node
	// 跳躍表的長度（除了第一個節(jié)點）
	length int64
	// 跳躍表的最大層級（除了第一個節(jié)點）
	level int16
}

創(chuàng)建跳躍表

// makeNode 創(chuàng)建一個跳躍表節(jié)點
func makeNode(level int16, score float64, member string) *node {
	n := &node{
		Element: Element{
			Score:  score,
			Member: member,
		},
		level: make([]*Level, level),
	}
	for i := range n.level {
		n.level[i] = new(Level)
	}
	return n
}
// makeSkiplist 創(chuàng)建一個跳躍表結(jié)構(gòu)
func makeSkiplist() *skiplist {
	return &skiplist{
		level:  1,
		header: makeNode(maxLevel, 0, ""),
	}
}

跳躍表的插入和刪除

在插入跳躍表之前，我們要明確的是新插入的這個節(jié)點，我們應(yīng)該在它之上建立多少層索引呢？我們將通過一個隨機算法來計算得到一個隨機值，叫做冪次定律。

冪次定律的含義是：如果某件事的發(fā)生頻率和它的某個屬性成冪關(guān)系，那么這個頻率就可以稱之為符合冪次定律。映射到我們的需求就是一個新插入的節(jié)點，生成小數(shù)值層數(shù)的概率很大，而生成大數(shù)值層數(shù)的概率很小。

const (
	maxLevel = 16
)
// randomLevel 隨機生成一個新跳躍表節(jié)點的層數(shù)（1~16）
// 滿足冪次定律
func randomLevel() int16 {
	level := int16(1)
	for float32(rand.Int31()&0xFFFF) < (0.25 * 0xFFFF) {
		level++
	}
	if level < maxLevel {
		return level
	}
	return maxLevel
}

上述函數(shù)計算出來的層數(shù)將呈現(xiàn)以下概率：

p = 0.25（1/4）

層數(shù)恰好為1的概率（不執(zhí)行while）為1 - p（3/4）.

層數(shù)恰好為2的概率（執(zhí)行 1 次while）為p * (1 - p)（3/16）.

層數(shù)恰好為3的概率（執(zhí)行 2 次while）為p ^ 2 * (1 - p)（3/64）.

層數(shù)恰好為4的概率（執(zhí)行 3 次while）為p ^ 3 * (1 - p)（3/256）.

層數(shù)恰好為k（k <= 32）的概率（執(zhí)行 k - 1 次while）為p ^ (k - 1) * (1 - p).

可以發(fā)現(xiàn)生成越高層數(shù)的概率會越來越小，而且和上一次呈冪關(guān)系遞減.

插入操作

插入操作的步驟：

  • 首先準備兩個切片：update（用于保存在每一層，待插入節(jié)點的前一個節(jié)點）、rank（用于累加每一層的跨度，方便后續(xù)待插入節(jié)點索引中span字段的計算）。
  • 從上至下遍歷每一層索引，在每一層中尋找待插入節(jié)點的位置（如果分數(shù)比當前節(jié)點小，就往后遍歷，比當前節(jié)點大就下沉），將待插入節(jié)點的前一個節(jié)點存到update切片中，然后將待插入節(jié)點相對起始點的便宜量粗存到rank切片中。
  • 找到待插入節(jié)點的位置之后，先使用randomLevel函數(shù)獲取該節(jié)點應(yīng)該建立索引的層數(shù)。
  • 接著構(gòu)造節(jié)點，然后插入到應(yīng)該插入的位置，首先需要更新每一層索引的狀態(tài)，新插入節(jié)點的forward指針就指向前一個節(jié)點的forward指針指向的位置（前一個節(jié)點保存在update切片中），新插入節(jié)點的索引span字段就是它與前一個節(jié)點同層索引的跨度之差（通過rank切片計算得到）。接著因為新插入節(jié)點增加了前面節(jié)點的跨度，所以需要更新前面一個節(jié)點每一層的跨度。
  • 最后設(shè)置新插入節(jié)點的backward指針指向，直接指向前一個節(jié)點即可（通過update切片來實現(xiàn)）。
// insert 插入元素
func (skiplist *skiplist) insert(member string, score float64) *node {
	// 保存在每一層，待插入節(jié)點的前一個節(jié)點
	update := make([]*node, maxLevel)
	// 用于累加跨度
	rank := make([]int64, maxLevel)
	// 找到待插入的位置
	node := skiplist.header
	for i := skiplist.level - 1; i >= 0; i-- {
		if i == skiplist.level-1 {
			rank[i] = 0
		} else {
			// 累加跨度
			rank[i] = rank[i+1]
		}
		if node.level[i] != nil {
			// 在第i層找待插入的位置
			for node.level[i].forward != nil &&
				(node.level[i].forward.Score < score ||
					(node.level[i].forward.Score == score && node.level[i].forward.Member < member)) { // same score, different key
				// 累加與前一個節(jié)點的跨度
				rank[i] += node.level[i].span
				// 前進
				node = node.level[i].forward
			}
		}
		update[i] = node
	}
	// 獲得隨機層數(shù)
	level := randomLevel()
	// 如果新插入的節(jié)點抽到的層級最大
	if level > skiplist.level {
		// 初始化每一層的狀態(tài)
		for i := skiplist.level; i < level; i++ {
			rank[i] = 0
			update[i] = skiplist.header
			update[i].level[i].span = skiplist.length
		}
		skiplist.level = level
	}
	// 構(gòu)造新節(jié)點并插入到跳表
	node = makeNode(level, score, member)
	for i := int16(0); i < level; i++ {
		node.level[i].forward = update[i].level[i].forward
		update[i].level[i].forward = node
		node.level[i].span = update[i].level[i].span - (rank[0] - rank[i])
		update[i].level[i].span = (rank[0] - rank[i]) + 1
	}
	// 新插入的節(jié)點增加了前面節(jié)點的跨度
	for i := level; i < skiplist.level; i++ {
		update[i].level[i].span++
	}
	// 設(shè)置回退節(jié)點
	if update[0] == skiplist.header {
		node.backward = nil
	} else {
		node.backward = update[0]
	}
	// 設(shè)置node前面一個節(jié)點的回退節(jié)點
	if node.level[0].forward != nil {
		node.level[0].forward.backward = node
	}
	skiplist.length++
	return node
}

刪除操作

刪除操作首先要找到待刪除節(jié)點的位置，找節(jié)點的步驟與插入節(jié)點的操作類似的，首先創(chuàng)建一個切片：update（用于保存在每一層，待刪除節(jié)點的前一個節(jié)點）。然后在每一層中進行查找，分數(shù)比當前節(jié)點小，就往后遍歷，比當前節(jié)點大就下沉，同時用update切片記錄每一層中待刪除節(jié)點的前一個節(jié)點。找到該節(jié)點之后，就可以進行刪除操作了。

先更新每一層索引的狀態(tài)：更新待刪除節(jié)點前一個節(jié)點的跨度以及forward指針的指向。

然后更新后面一個節(jié)點的回退指針，最后更新跳表中的最大層級即可。

// 尋找待刪除的節(jié)點
func (skiplist *skiplist) remove(member string, score float64) bool {
	// 儲存待刪除節(jié)點每一層的上一個節(jié)點
	update := make([]*node, maxLevel)
	node := skiplist.header
	// 尋找待刪除節(jié)點
	for i := skiplist.level - 1; i >= 0; i-- {
		for node.level[i].forward != nil &&
			(node.level[i].forward.Score < score ||
				(node.level[i].forward.Score == score &&
					node.level[i].forward.Member < member)) {
			node = node.level[i].forward
		}
		update[i] = node
	}
	// node在循環(huán)中，一直是待刪除節(jié)點的前一個節(jié)點
	// 在最底層的索引處向后移動一位，剛好就是待刪除節(jié)點
	node = node.level[0].forward
	// 找到該節(jié)點
	if node != nil && score == node.Score && node.Member == member {
		skiplist.removeNode(node, update)
		return true
	}
	return false
}
// 刪除找到的節(jié)點
func (skiplist *skiplist) removeNode(node *node, update []*node) {
	// 更新每一層的狀態(tài)
	for i := int16(0); i < skiplist.level; i++ {
		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--
		}
	}
	// 更新后面一個節(jié)點的回退指針
	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--
}

跳躍表的排名操作

獲取元素的排名

獲取元素的排名操作比較簡單，首先定義一個rank整型變量，用于在遍歷的時候累加跨度。

接著逐層進行查找，在某一層進行查找時，每往前遍歷一個元素，就使用rank變量累加上它們索引之間的跨度，當遍歷到第0層時，就找到了這個節(jié)點，rank變量就是當前節(jié)點在整個跳躍表中的排名。

func (skiplist *skiplist) getRank(member string, score float64) int64 {
	var rank int64 = 0
	x := skiplist.header
	for i := skiplist.level - 1; i >= 0; i-- {
		for x.level[i].forward != nil &&
			(x.level[i].forward.Score < score ||
				(x.level[i].forward.Score == score &&
					x.level[i].forward.Member <= member)) {
			rank += x.level[i].span
			x = x.level[i].forward
		}
		if x.Member == member {
			return rank
		}
	}
	return 0
}

通過排名獲取元素

首先定義一個變量i用于累加每一層索引的跨度，接著在每一層索引中進行遍歷，如果i累加上當前節(jié)點層與下一個節(jié)點層的跨度值小于rank，就繼續(xù)往后遍歷，否則就下沉。當i等于rank時，就找到了該節(jié)點。

func (skiplist *skiplist) getByRank(rank int64) *node {
	// 記錄從頭節(jié)點開始的跨度
	var i int64 = 0
	// 用于遍歷節(jié)點的指針
	n := skiplist.header
	// 從最高層級開始遍歷
	for level := skiplist.level - 1; level >= 0; level-- {
		for n.level[level].forward != nil && (i+n.level[level].span) <= rank {
			i += n.level[level].span
			n = n.level[level].forward
		}
		if i == rank {
			return n
		}
	}
	return nil
}

跳躍表的區(qū)間操作

我們創(chuàng)建了一個ScoreBorder結(jié)構(gòu)體用于封裝跳表的分數(shù)，提供了比較大小以及創(chuàng)建ScoreBorder等API。

const (
	// 負無窮
	negativeInf int8 = -1
	// 正無窮
	positiveInf int8 = 1
)
type ScoreBorder struct {
	// 標記當前分數(shù)是否為無窮
	Inf int8
	// 分數(shù)值
	Value float64
	// 標記兩個分數(shù)相等時，是否返回true
	Exclude bool
}
func (border *ScoreBorder) greater(value float64) bool {
	if border.Inf == negativeInf {
		return false
	} else if border.Inf == positiveInf {
		return true
	}
	if border.Exclude {
		return border.Value > value
	}
	return border.Value >= value
}
func (border *ScoreBorder) less(value float64) bool {
	if border.Inf == negativeInf {
		return true
	} else if border.Inf == positiveInf {
		return false
	}
	if border.Exclude {
		return border.Value < value
	}
	return border.Value <= value
}
var positiveInfBorder = &ScoreBorder{
	Inf: positiveInf,
}
var negativeInfBorder = &ScoreBorder{
	Inf: negativeInf,
}
// ParseScoreBorder 根據(jù)參數(shù)構(gòu)造并返回ScoreBorder
func ParseScoreBorder(s string) (*ScoreBorder, error) {
	if s == "inf" || s == "+inf" {
		return positiveInfBorder, nil
	}
	if s == "-inf" {
		return negativeInfBorder, nil
	}
	if s[0] == '(' {
		value, err := strconv.ParseFloat(s[1:], 64)
		if err != nil {
			return nil, errors.New("ERR min or max is not a float")
		}
		return &ScoreBorder{
			Inf:     0,
			Value:   value,
			Exclude: true,
		}, nil
	}
	value, err := strconv.ParseFloat(s, 64)
	if err != nil {
		return nil, errors.New("ERR min or max is not a float")
	}
	return &ScoreBorder{
		Inf:     0,
		Value:   value,
		Exclude: false,
	}, nil
}

判斷[min, max]區(qū)間與是否在skiplist的分數(shù)區(qū)間內(nèi)（是否有重合）

判斷有三個指標：

  • 判斷[min, max]區(qū)間本身是否有效。
  • 判斷min是否大于跳表的最大分數(shù)值（與表尾元素的分數(shù)作比較）。
  • 判斷max是否小于跳表的最小分數(shù)值（與表頭元素的分數(shù)作比較）。
func (skiplist *skiplist) hasInRange(min *ScoreBorder, max *ScoreBorder) bool {
	// [min, max]無意義或為空
	if min.Value > max.Value || (min.Value == max.Value && (min.Exclude || max.Exclude)) {
		return false
	}
	// [min, max] > skiplist.tail.Score
	n := skiplist.tail
	if n == nil || !min.less(n.Score) {
		return false
	}
	// [min, max] < skiplist.head.Score
	n = skiplist.header.level[0].forward
	if n == nil || !max.greater(n.Score) {
		return false
	}
	return true
}

從跳表中找到處于[min, max]區(qū)間的最小值

實現(xiàn)思路比較簡單，我們找到跳表中分數(shù)第一個大于min的節(jié)點即可。找到之后我們還需要將該節(jié)點的分數(shù)與max作比較，如果大于max，則不存在。

func (skiplist *skiplist) getFirstInScoreRange(min *ScoreBorder, max *ScoreBorder) *node {
	if !skiplist.hasInRange(min, max) {
		return nil
	}
	n := skiplist.header
	// 找到第一個大于等于min的節(jié)點
	for level := skiplist.level - 1; level >= 0; level-- {
		for n.level[level].forward != nil && !min.less(n.level[level].forward.Score) {
			n = n.level[level].forward
		}
	}
	n = n.level[0].forward
	// n節(jié)點的分數(shù)在[min, max]區(qū)間之外
	if !max.greater(n.Score) {
		return nil
	}
	return n
}

刪除跳表中分數(shù)值處在[min, max]區(qū)間內(nèi)的元素，并返回它們的切片

首先遍歷跳表，然后找到分數(shù)值大于min的第一個節(jié)點，從這個節(jié)點開始刪除，刪除一個就繼續(xù)往后遍歷，刪除的過程中還得判斷，待刪除的節(jié)點分數(shù)是否超出了[min, max]區(qū)間。

func (skiplist *skiplist) RemoveRangeByScore(min *ScoreBorder, max *ScoreBorder) (removed []*Element) {
	// 儲存待刪除節(jié)點每一層的前驅(qū)節(jié)點
	update := make([]*node, maxLevel)
	removed = make([]*Element, 0)
	// 找到待刪除節(jié)點每一層的前驅(qū)節(jié)點
	node := skiplist.header
	for i := skiplist.level - 1; i >= 0; i-- {
		for node.level[i].forward != nil {
			if min.less(node.level[i].forward.Score) {
				break
			}
			node = node.level[i].forward
		}
		update[i] = node
	}
	node = node.level[0].forward
	// 開始刪除節(jié)點
	for node != nil {
		// 保證不超出[min, max]區(qū)間
		if !max.greater(node.Score) {
			break
		}
		next := node.level[0].forward
		removedElement := node.Element
		removed = append(removed, &removedElement)
		skiplist.removeNode(node, update)
		node = next
	}
	return removed
}

刪除排名在[start, stop]區(qū)間內(nèi)的元素，并返回它們的切片

首先定義一個i變量，作為刪除節(jié)點的迭代器，接著找到排名為start的節(jié)點，然后從這個節(jié)點往后刪除即可。

func (skiplist *skiplist) RemoveRangeByRank(start int64, stop int64) (removed []*Element) {
	// 排名迭代器
	var i int64 = 0
	update := make([]*node, maxLevel)
	removed = make([]*Element, 0)
	// 找到待刪除的第一個節(jié)點的前驅(qū)節(jié)點，并儲存在update切片中
	node := skiplist.header
	for level := skiplist.level - 1; level >= 0; level-- {
		for node.level[level].forward != nil && (i+node.level[level].span) < start {
			i += node.level[level].span
			node = node.level[level].forward
		}
		update[level] = node
	}
	i++
	// 處在區(qū)間的第一個節(jié)點
	node = node.level[0].forward
	// 開始刪除節(jié)點
	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
}

完整實現(xiàn)

https://github.com/omlight95/GoRedis/blob/master/datastruct/sortedset/skiplist.go

原文鏈接：https://blog.csdn.net/qq_49723651/article/details/127624075

欄目分類
最近更新