GoLang完整實現(xiàn)快速列表
更新時間：2022年12月17日 15:18:00 作者：Onemorelight95
這篇文章主要介紹了GoLang完整實現(xiàn)快速列表，列表是一種非連續(xù)的存儲容器，由多個節(jié)點組成，節(jié)點通過一些 變量 記錄彼此之間的關(guān)系，列表有多種實現(xiàn)方法，如單鏈表、雙鏈表等
快速列表介紹
快速列表（quicklist）是Redis中特有的一種數(shù)據(jù)結(jié)構(gòu)，主要是為了解決雙端鏈表的弊端：雙端鏈表的附加空間比較高，因為prev和next指針會占掉一部分的空間（64位系統(tǒng)占用8 + 8 = 16字節(jié)）.而且鏈表的每個節(jié)點都是單獨分配內(nèi)存，會加劇內(nèi)存的碎片化。
Redis中的快速列表實際上是zipList（經(jīng)過優(yōu)化過的數(shù)組）和linkedList的混合體，它把zipList放在linkedList的每個結(jié)點中，實現(xiàn)緊湊存儲。如下圖所示：
實現(xiàn)快速列表
快速列表的結(jié)構(gòu)
由于Go語言自帶slice這種操作方便的“動態(tài)數(shù)組”結(jié)構(gòu)，所以我給鏈表的每個節(jié)點中都分配一個容量為1024大小的切片，那么一個鏈表節(jié)點就可以看作是一頁，頁大小就是1024。
頁大小
首先定義頁大小為1024：
// pageSize 一頁的大小 const pageSize = 1024
表頭結(jié)構(gòu)
// QuickList 快速列表是在頁（切片）之上建立的鏈表
// QuickList 比普通鏈表的插入、遍歷以及內(nèi)存有著更好的性能
type QuickList struct {
data *list.List // 每一頁就是interface{}的切片，大小為1024
size int
}
表頭結(jié)構(gòu)中的data字段直接使用了Go語言list包中的List結(jié)構(gòu)：
// 雙向鏈表標頭結(jié)構(gòu)
type List struct {
root Element // 哨兵節(jié)點
len int // 鏈表的節(jié)點個數(shù)
}
// 雙向鏈表的節(jié)點
type Element struct {
// 前向和后向指針
next, prev *Element
// 表頭結(jié)構(gòu)
list *List
// 值域
Value interface{}
}
Go語言自帶的list包實現(xiàn)了對雙向鏈表的封裝，雙向鏈表的節(jié)點元素是interface{}類型，利用這種方式實現(xiàn)了泛型。
我們對快速列表的實現(xiàn)，使得上述雙向鏈表節(jié)點中存儲的實際上是容量為1024的切片，此后對于鏈表的相關(guān)操作，直接調(diào)用list包向外暴露的API即可。
快速列表的迭代器
快速列表的迭代器中有三個字段：鏈表的節(jié)點node（可以看成一頁），元素在頁中的偏移量、表頭結(jié)構(gòu)。
這樣實現(xiàn)的迭代器，使得迭代器既可以在元素之前迭代，也可以在頁之間快速迭代。
// iterator 快速列表的迭代器，在[-1, ql.Len()]之間迭代
type iterator struct {
// 快速列表的一頁
node *list.Element
// 元素下標在頁中的偏移量
offset int
ql *QuickList
}使用迭代器返回一個元素
使用迭代器返回一個元素的復雜度為O(1)，一個元素的位置可以通過 頁的位置 + 該元素在頁中的位置 快速定位。
// 使用迭代器返回一個元素
func (iter *iterator) get() interface{} {
return iter.page()[iter.offset]
}
返回迭代器對應的那一頁
上面我們說過，鏈表的節(jié)點元素其實就是一個容量為1024的slice，通過類型斷言直接返回即可。
// 返回迭代器對應的那一頁
func (iter *iterator) page() []interface{} {
return iter.node.Value.([]interface{})
}
根據(jù)元素下標返回對應的迭代器
快速列表查找元素效率比雙向列表要快，首先利用迭代器一頁一頁進行迭代，當確定了元素在哪一頁后，利用元素的下標直接在頁內(nèi)的slice中直接定位即可。
func (ql *QuickList) find(index int) *iterator {
if ql == nil {
panic("list is nil")
}
if index < 0 || index >= ql.size {
panic("index out of bound")
}
var n *list.Element
// 保存當前頁的所有元素
var page []interface{}
// 累加遍歷到當前頁為止，前面的所有元素數(shù)量
var pageBeg int
if index < ql.size/2 {
// 從表頭進行查找
n = ql.data.Front()
pageBeg = 0
for {
page = n.Value.([]interface{})
if pageBeg+len(page) > index {
break
}
pageBeg += len(page)
n = n.Next()
}
} else {
// 從表尾進行查找
n = ql.data.Back()
pageBeg = ql.size
for {
page = n.Value.([]interface{})
pageBeg -= len(page)
if pageBeg <= index {
break
}
n = n.Prev()
}
}
pageOffset := index - pageBeg
return &iterator{
node: n,
offset: pageOffset,
ql: ql,
}
}
向后迭代一位
// next 頁內(nèi)迭代器，向后迭代一位
// 如果當前元素下標未出界且不在最后一位，就向后移動一位，返回true
// 如果當前元素下標在快速列表的最后一頁且是最后一個元素，直接返回false
// 如果當前元素下標不在快速列表的最后一頁，但是是當前頁的最后一個元素，跳轉(zhuǎn)到下一頁，返回true
func (iter *iterator) next() bool {
// 得到迭代器對應的那一頁
page := iter.page()
// 當前位置未出界且不在最后一位，就向后移動一位，返回true
if iter.offset < len(page)-1 {
iter.offset++
return true
}
// 當前元素在快速列表的最后一頁且是最后一個元素，直接返回false
if iter.node == iter.ql.data.Back() {
// already at last node
iter.offset = len(page)
return false
}
// 當前元素不在快速列表的最后一頁，但是是當前頁的最后一個元素，跳轉(zhuǎn)到下一頁，返回true
iter.offset = 0
iter.node = iter.node.Next()
return true
}
往前迭代一位
// prev 頁內(nèi)迭代器，向前迭代一位
func (iter *iterator) prev() bool {
if iter.offset > 0 {
iter.offset--
return true
}
if iter.node == iter.ql.data.Front() {
iter.offset = -1
return false
}
iter.node = iter.node.Prev()
prevPage := iter.node.Value.([]interface{})
iter.offset = len(prevPage) - 1
return true
}
添加和插入元素
向表尾添加一個元素
向表尾添加元素需要考慮三種情況：
- 列表是空的，創(chuàng)建新的一頁，添加到表尾即可。
- 表尾節(jié)點那一頁是滿的，獲取表尾節(jié)點，創(chuàng)建新的一頁，添加到表尾節(jié)點的后面即可。
- 表尾節(jié)點那一頁不是滿的，正常添加到表尾即可。
// Add 添加元素到表尾
func (ql *QuickList) Add(val interface{}) {
ql.size++
// 列表是空的
if ql.data.Len() == 0 {
page := make([]interface{}, 0, pageSize)
page = append(page, val)
ql.data.PushBack(page)
return
}
// 獲取表尾節(jié)點
backNode := ql.data.Back()
backPage := backNode.Value.([]interface{})
// 表尾節(jié)點頁滿了，需要新創(chuàng)建一頁
if len(backPage) == cap(backPage) {
page := make([]interface{}, 0, pageSize)
page = append(page, val)
ql.data.PushBack(page)
return
}
// 默認將節(jié)點添加進表尾頁中
backPage = append(backPage, val)
backNode.Value = backPage
}
根據(jù)下標插入一個元素
// Insert 插入元素
// 插入元素的策略分三種情況：
// 1. 向最后一頁的最后一個位置插入元素，直接掉用ql.Add()插入即可
// 2. 某一頁插入一個元素，且該頁未滿，直接插入該頁即可
// 3. 某一頁插入一個元素，該頁滿了，就新創(chuàng)建一頁，然后將前512個元素留在原來那頁，將后512個元素移到新的頁中，
// 新插入的元素，如果下標在[0,512]之間，就插入到原來頁，如果下標在[516, 1024]之間，就插入到新創(chuàng)建的頁中
func (ql *QuickList) Insert(index int, val interface{}) {
// 向表尾插入元素
if index == ql.size {
ql.Add(val)
return
}
iter := ql.find(index)
page := iter.node.Value.([]interface{})
// 如果待插入頁的元素小于1024，直接插入到該頁即可
if len(page) < pageSize {
// insert into not full page
page = append(page[:iter.offset+1], page[iter.offset:]...)
page[iter.offset] = val
iter.node.Value = page
ql.size++
return
}
// 待插入頁的元素已經(jīng)滿1024，就需要新創(chuàng)建一頁
var nextPage []interface{}
// 后一半的元素放在新創(chuàng)建的頁中，前一半元素放在原來的頁中
nextPage = append(nextPage, page[pageSize/2:]...) // pageSize must be even
page = page[:pageSize/2]
// 待插入元素的下標小于512，插到前面那頁
if iter.offset < len(page) {
page = append(page[:iter.offset+1], page[iter.offset:]...)
page[iter.offset] = val
} else {
// 待插入元素的下標大于512，插到后面那頁
i := iter.offset - pageSize/2
nextPage = append(nextPage[:i+1], nextPage[i:]...)
nextPage[i] = val
}
// 儲存當前頁和新創(chuàng)建的下一頁
iter.node.Value = page
ql.data.InsertAfter(nextPage, iter.node)
ql.size++
}
刪除元素
// 刪除元素
// 刪除元素分為三種情況：
// 1.刪除后的頁不為空，且刪除的不是該頁的最后一個元素，什么都不用管
// 2.刪除后的頁不為空，且刪除的是該頁的最后一個元素，需要將迭代器移動到下一頁的最后一個元素
// 3.刪除的頁為空（需要刪除該頁），且刪除的頁是最后一頁，將迭代器置空
// 4.刪除的頁為空（需要刪除該頁），且刪除的頁不是最后一頁，將迭代器指向下一頁
func (iter *iterator) remove() interface{} {
page := iter.page()
val := page[iter.offset]
// 先直接在頁中刪除這個元素
page = append(page[:iter.offset], page[iter.offset+1:]...)
// 如果刪除后的頁不為空，只更新iter.offset即可
if len(page) > 0 {
iter.node.Value = page
// 如果刪除的是頁中的最后一個元素，那么迭代器需要移動到下一頁的第一個元素
if iter.offset == len(page) {
if iter.node != iter.ql.data.Back() {
iter.node = iter.node.Next()
iter.offset = 0
}
}
} else {
// 如果刪除后的頁為空，需要刪除該頁
// 如果刪除的是最后一頁，迭代器需要置空
if iter.node == iter.ql.data.Back() {
iter.ql.data.Remove(iter.node)
iter.node = nil
iter.offset = 0
} else {
// 如果刪除的不是最后一頁，迭代器需要指向下一頁
nextNode := iter.node.Next()
iter.ql.data.Remove(iter.node)
iter.node = nextNode
iter.offset = 0
}
}
iter.ql.size--
return val
}
遍歷快速列表
// Consumer 用于遍歷中斷的函數(shù)，返回true表示繼續(xù)遍歷，可以在Consumer中調(diào)用自定義函數(shù)
type Consumer func(i int, v interface{}) bool
// ForEach 遍歷快速列表中的元素
// 如果consumer返回false，結(jié)束遍歷
func (ql *QuickList) ForEach(consumer Consumer) {
if ql == nil {
panic("list is nil")
}
if ql.Len() == 0 {
return
}
iter := ql.find(0)
i := 0
for {
goNext := consumer(i, iter.get())
if !goNext {
break
}
i++
// 遍歷到表尾，結(jié)束
if !iter.next() {
break
}
}
}
完整實現(xiàn)
https://github.com/omlight95/GoRedis/blob/master/datastruct/list/quicklist.go
到此這篇關(guān)于GoLang完整實現(xiàn)快速列表的文章就介紹到這了,更多相關(guān)Go快速列表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
您可能感興趣的文章:
相關(guān)文章
最近開發(fā)的時候遇到這么個問題,就是在window上獲取了文件目錄的字段,然后將這個絕對路徑保存到數(shù)據(jù)庫,但是前端展示的時候路徑的雙反斜杠變成了單反斜杠,本文給大家介紹了使用go語言將單反斜杠改為雙反斜杠的方法,需要的朋友可以參考下2024-01-01
這篇文章主要介紹了Go語言實現(xiàn)機器大小端判斷代碼分享,本文直接給出實現(xiàn)代碼,需要的朋友可以參考下2014-10-10
本文主要介紹了go項目中環(huán)境變量的配置，文中通過示例代碼介紹的非常詳細，需要的朋友們下面隨著小編來一起學習學習吧2021-07-07
這篇文章主要為大家介紹了go語言題解LeetCode66加一示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-12-12
這篇文章主要為大家介紹了Go語言輕松編寫高效可靠的并發(fā)程序?qū)崿F(xiàn)示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-05-05
函數(shù)是編程中不可或缺的組成部分，在本文中，我們將詳細介紹Go語言中函數(shù)的概念和使用方法，包括函數(shù)的定義、參數(shù)和返回值等，需要的可以參考一下2023-06-06
平時開發(fā)過程中,時間相關(guān)的操作用的還是很多的,下面這篇文章主要給大家介紹了關(guān)于Go時間操作常用方法的相關(guān)資料,文中通過實例代碼介紹的非常詳細,需要的朋友可以參考下2023-06-06
Go并發(fā)編程中的錯誤恢復機制與代碼持續(xù)執(zhí)行實例探索
這篇文章主要為大家介紹了Go并發(fā)編程中的錯誤恢復機制與代碼持續(xù)執(zhí)行實例探索,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2024-01-01
這篇文章主要為大家介紹了Go語言入門Go?Web?Fiber框架的示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-05-05
這篇文章主要為大家介紹了Go中過濾范型集合性能示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-03-03